/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench/egcd2-ll.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-5d317bd [2022-03-18 22:43:48,621 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-18 22:43:48,628 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-18 22:43:48,660 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-18 22:43:48,660 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-18 22:43:48,661 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-18 22:43:48,662 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-18 22:43:48,663 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-18 22:43:48,664 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-18 22:43:48,665 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-18 22:43:48,665 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-18 22:43:48,666 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-18 22:43:48,666 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-18 22:43:48,672 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-18 22:43:48,673 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-18 22:43:48,676 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-18 22:43:48,676 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-18 22:43:48,679 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-18 22:43:48,685 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-18 22:43:48,686 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-18 22:43:48,686 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-18 22:43:48,689 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-18 22:43:48,690 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-18 22:43:48,690 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-18 22:43:48,691 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-18 22:43:48,692 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-18 22:43:48,693 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-18 22:43:48,693 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-18 22:43:48,693 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-18 22:43:48,694 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-18 22:43:48,694 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-18 22:43:48,694 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-18 22:43:48,695 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-18 22:43:48,695 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-18 22:43:48,696 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-18 22:43:48,696 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-18 22:43:48,696 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-18 22:43:48,697 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-18 22:43:48,697 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-18 22:43:48,697 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-18 22:43:48,698 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-18 22:43:48,703 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-18 22:43:48,704 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-03-18 22:43:48,727 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-18 22:43:48,727 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-18 22:43:48,728 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-18 22:43:48,729 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-18 22:43:48,729 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-18 22:43:48,729 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-18 22:43:48,730 INFO L138 SettingsManager]: * Use SBE=true [2022-03-18 22:43:48,730 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-18 22:43:48,730 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-18 22:43:48,730 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-18 22:43:48,731 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-18 22:43:48,731 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-18 22:43:48,731 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-18 22:43:48,731 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-18 22:43:48,731 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-18 22:43:48,731 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-18 22:43:48,731 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-18 22:43:48,731 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-18 22:43:48,731 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-18 22:43:48,731 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-18 22:43:48,732 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-18 22:43:48,732 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-03-18 22:43:48,732 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-18 22:43:48,732 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-18 22:43:48,732 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-18 22:43:48,732 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-18 22:43:48,732 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-03-18 22:43:48,733 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-03-18 22:43:48,733 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-18 22:43:48,733 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_QVASR WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-03-18 22:43:48,897 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-18 22:43:48,925 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-18 22:43:48,926 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-18 22:43:48,927 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-18 22:43:48,928 INFO L275 PluginConnector]: CDTParser initialized [2022-03-18 22:43:48,928 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench/egcd2-ll.c [2022-03-18 22:43:48,999 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9cae08e0c/b0878632ddcd46e8988c0db3eae668be/FLAG2133be7fe [2022-03-18 22:43:49,313 INFO L306 CDTParser]: Found 1 translation units. [2022-03-18 22:43:49,314 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench/egcd2-ll.c [2022-03-18 22:43:49,324 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9cae08e0c/b0878632ddcd46e8988c0db3eae668be/FLAG2133be7fe [2022-03-18 22:43:49,333 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9cae08e0c/b0878632ddcd46e8988c0db3eae668be [2022-03-18 22:43:49,335 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-18 22:43:49,335 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-18 22:43:49,336 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-18 22:43:49,337 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-18 22:43:49,339 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-18 22:43:49,339 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.03 10:43:49" (1/1) ... [2022-03-18 22:43:49,340 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@518eb056 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 10:43:49, skipping insertion in model container [2022-03-18 22:43:49,340 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.03 10:43:49" (1/1) ... [2022-03-18 22:43:49,344 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-18 22:43:49,354 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-18 22:43:49,500 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench/egcd2-ll.c[490,503] [2022-03-18 22:43:49,514 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-18 22:43:49,519 INFO L203 MainTranslator]: Completed pre-run [2022-03-18 22:43:49,526 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench/egcd2-ll.c[490,503] [2022-03-18 22:43:49,531 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-18 22:43:49,539 INFO L208 MainTranslator]: Completed translation [2022-03-18 22:43:49,539 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 10:43:49 WrapperNode [2022-03-18 22:43:49,539 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-18 22:43:49,540 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-18 22:43:49,540 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-18 22:43:49,540 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-18 22:43:49,547 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 10:43:49" (1/1) ... [2022-03-18 22:43:49,547 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 10:43:49" (1/1) ... [2022-03-18 22:43:49,551 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 10:43:49" (1/1) ... [2022-03-18 22:43:49,551 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 10:43:49" (1/1) ... [2022-03-18 22:43:49,554 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 10:43:49" (1/1) ... [2022-03-18 22:43:49,556 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 10:43:49" (1/1) ... [2022-03-18 22:43:49,557 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 10:43:49" (1/1) ... [2022-03-18 22:43:49,558 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-18 22:43:49,559 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-18 22:43:49,559 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-18 22:43:49,559 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-18 22:43:49,559 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 10:43:49" (1/1) ... [2022-03-18 22:43:49,564 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-18 22:43:49,572 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:43:49,581 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-03-18 22:43:49,590 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-03-18 22:43:49,611 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-18 22:43:49,611 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-18 22:43:49,611 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-18 22:43:49,611 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-18 22:43:49,611 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-18 22:43:49,611 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-18 22:43:49,612 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-18 22:43:49,612 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-18 22:43:49,612 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-18 22:43:49,612 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-18 22:43:49,613 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-03-18 22:43:49,613 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-18 22:43:49,613 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-18 22:43:49,613 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-18 22:43:49,613 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-18 22:43:49,613 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-18 22:43:49,613 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-18 22:43:49,613 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-18 22:43:49,613 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-18 22:43:49,613 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-18 22:43:49,654 INFO L234 CfgBuilder]: Building ICFG [2022-03-18 22:43:49,655 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-18 22:43:49,738 INFO L275 CfgBuilder]: Performing block encoding [2022-03-18 22:43:49,742 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-18 22:43:49,742 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-18 22:43:49,743 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.03 10:43:49 BoogieIcfgContainer [2022-03-18 22:43:49,743 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-18 22:43:49,744 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-18 22:43:49,744 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-18 22:43:49,744 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-18 22:43:49,746 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.03 10:43:49" (1/1) ... [2022-03-18 22:43:49,758 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 18.03 10:43:49 BasicIcfg [2022-03-18 22:43:49,758 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-18 22:43:49,759 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-18 22:43:49,759 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-18 22:43:49,761 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-18 22:43:49,761 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.03 10:43:49" (1/4) ... [2022-03-18 22:43:49,762 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@241b4393 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.03 10:43:49, skipping insertion in model container [2022-03-18 22:43:49,762 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 10:43:49" (2/4) ... [2022-03-18 22:43:49,762 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@241b4393 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.03 10:43:49, skipping insertion in model container [2022-03-18 22:43:49,762 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.03 10:43:49" (3/4) ... [2022-03-18 22:43:49,762 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@241b4393 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.03 10:43:49, skipping insertion in model container [2022-03-18 22:43:49,762 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 18.03 10:43:49" (4/4) ... [2022-03-18 22:43:49,763 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll.cqvasr [2022-03-18 22:43:49,766 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-03-18 22:43:49,767 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-18 22:43:49,811 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-18 22:43:49,815 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-03-18 22:43:49,815 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-18 22:43:49,844 INFO L276 IsEmpty]: Start isEmpty. Operand has 37 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 21 states have internal predecessors, (28), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-18 22:43:49,847 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-03-18 22:43:49,847 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:43:49,848 INFO L500 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] [2022-03-18 22:43:49,848 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:43:49,851 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:43:49,851 INFO L85 PathProgramCache]: Analyzing trace with hash -876857705, now seen corresponding path program 1 times [2022-03-18 22:43:49,872 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:43:49,872 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [427401390] [2022-03-18 22:43:49,873 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:49,873 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:43:49,963 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:49,999 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-18 22:43:50,002 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:50,008 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-18 22:43:50,009 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:50,013 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-03-18 22:43:50,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:50,018 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-18 22:43:50,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:50,026 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-03-18 22:43:50,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:50,037 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-18 22:43:50,037 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:43:50,038 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [427401390] [2022-03-18 22:43:50,038 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [427401390] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 22:43:50,038 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 22:43:50,038 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-18 22:43:50,040 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1743561137] [2022-03-18 22:43:50,040 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 22:43:50,043 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-18 22:43:50,043 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:43:50,063 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-18 22:43:50,064 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-18 22:43:50,065 INFO L87 Difference]: Start difference. First operand has 37 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 21 states have internal predecessors, (28), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 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) [2022-03-18 22:43:50,160 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:43:50,161 INFO L93 Difference]: Finished difference Result 67 states and 106 transitions. [2022-03-18 22:43:50,162 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-18 22:43:50,163 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 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 32 [2022-03-18 22:43:50,164 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:43:50,168 INFO L225 Difference]: With dead ends: 67 [2022-03-18 22:43:50,168 INFO L226 Difference]: Without dead ends: 32 [2022-03-18 22:43:50,171 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-18 22:43:50,173 INFO L912 BasicCegarLoop]: 36 mSDtfsCounter, 19 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 39 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 22:43:50,174 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 39 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 22:43:50,187 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-03-18 22:43:50,212 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-03-18 22:43:50,212 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-18 22:43:50,213 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2022-03-18 22:43:50,214 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 32 [2022-03-18 22:43:50,214 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:43:50,215 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2022-03-18 22:43:50,215 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 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) [2022-03-18 22:43:50,215 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-03-18 22:43:50,216 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-03-18 22:43:50,216 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:43:50,216 INFO L500 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] [2022-03-18 22:43:50,216 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-18 22:43:50,217 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:43:50,217 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:43:50,217 INFO L85 PathProgramCache]: Analyzing trace with hash -1858806609, now seen corresponding path program 1 times [2022-03-18 22:43:50,217 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:43:50,218 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [461972752] [2022-03-18 22:43:50,218 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:50,218 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:43:50,246 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:43:50,247 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1266575386] [2022-03-18 22:43:50,247 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:50,247 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:50,247 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:43:50,249 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:43:50,250 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-18 22:43:50,295 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:50,296 INFO L263 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-18 22:43:50,300 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:43:50,471 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-03-18 22:43:50,472 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:43:50,584 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-03-18 22:43:50,584 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:43:50,585 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [461972752] [2022-03-18 22:43:50,585 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:43:50,585 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1266575386] [2022-03-18 22:43:50,593 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1266575386] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 22:43:50,594 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 22:43:50,595 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2022-03-18 22:43:50,598 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1479323672] [2022-03-18 22:43:50,599 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 22:43:50,602 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-18 22:43:50,603 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:43:50,603 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-18 22:43:50,603 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-18 22:43:50,603 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-18 22:43:50,700 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:43:50,700 INFO L93 Difference]: Finished difference Result 49 states and 64 transitions. [2022-03-18 22:43:50,700 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-18 22:43:50,700 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-03-18 22:43:50,701 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:43:50,701 INFO L225 Difference]: With dead ends: 49 [2022-03-18 22:43:50,701 INFO L226 Difference]: Without dead ends: 41 [2022-03-18 22:43:50,702 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 59 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-03-18 22:43:50,703 INFO L912 BasicCegarLoop]: 35 mSDtfsCounter, 19 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 62 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 173 SdHoareTripleChecker+Invalid, 73 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 62 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 22:43:50,703 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 173 Invalid, 73 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 62 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 22:43:50,711 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-03-18 22:43:50,717 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 34. [2022-03-18 22:43:50,717 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-18 22:43:50,718 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 43 transitions. [2022-03-18 22:43:50,718 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 43 transitions. Word has length 33 [2022-03-18 22:43:50,718 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:43:50,719 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 43 transitions. [2022-03-18 22:43:50,719 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-18 22:43:50,719 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 43 transitions. [2022-03-18 22:43:50,719 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-03-18 22:43:50,719 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:43:50,719 INFO L500 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] [2022-03-18 22:43:50,749 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-18 22:43:50,935 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:50,936 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:43:50,937 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:43:50,937 INFO L85 PathProgramCache]: Analyzing trace with hash -1753102734, now seen corresponding path program 1 times [2022-03-18 22:43:50,937 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:43:50,937 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [86053336] [2022-03-18 22:43:50,938 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:50,938 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:43:50,952 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:43:50,953 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1687857179] [2022-03-18 22:43:50,953 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:50,953 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:50,953 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:43:50,957 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:43:50,958 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-18 22:43:50,999 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:51,000 INFO L263 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-18 22:43:51,002 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:43:51,096 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-03-18 22:43:51,096 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:43:51,170 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-18 22:43:51,171 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:43:51,171 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [86053336] [2022-03-18 22:43:51,171 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:43:51,171 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1687857179] [2022-03-18 22:43:51,171 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1687857179] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-18 22:43:51,171 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-18 22:43:51,171 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-03-18 22:43:51,172 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [156248377] [2022-03-18 22:43:51,172 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 22:43:51,172 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 22:43:51,172 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:43:51,172 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 22:43:51,173 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2022-03-18 22:43:51,173 INFO L87 Difference]: Start difference. First operand 34 states and 43 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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) [2022-03-18 22:43:51,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:43:51,201 INFO L93 Difference]: Finished difference Result 40 states and 48 transitions. [2022-03-18 22:43:51,202 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 22:43:51,202 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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 34 [2022-03-18 22:43:51,202 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:43:51,203 INFO L225 Difference]: With dead ends: 40 [2022-03-18 22:43:51,203 INFO L226 Difference]: Without dead ends: 38 [2022-03-18 22:43:51,203 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 58 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-03-18 22:43:51,204 INFO L912 BasicCegarLoop]: 35 mSDtfsCounter, 6 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 22:43:51,204 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 126 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 22:43:51,205 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2022-03-18 22:43:51,208 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2022-03-18 22:43:51,209 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 22 states have internal predecessors, (24), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-18 22:43:51,209 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 46 transitions. [2022-03-18 22:43:51,210 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 46 transitions. Word has length 34 [2022-03-18 22:43:51,210 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:43:51,210 INFO L478 AbstractCegarLoop]: Abstraction has 38 states and 46 transitions. [2022-03-18 22:43:51,210 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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) [2022-03-18 22:43:51,210 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 46 transitions. [2022-03-18 22:43:51,211 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-03-18 22:43:51,211 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:43:51,211 INFO L500 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] [2022-03-18 22:43:51,228 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-18 22:43:51,428 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-03-18 22:43:51,429 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:43:51,429 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:43:51,429 INFO L85 PathProgramCache]: Analyzing trace with hash -742626026, now seen corresponding path program 1 times [2022-03-18 22:43:51,429 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:43:51,429 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1447324421] [2022-03-18 22:43:51,429 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:51,433 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:43:51,441 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:43:51,442 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [105529566] [2022-03-18 22:43:51,442 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:51,442 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:51,442 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:43:51,443 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:43:51,447 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-18 22:43:51,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:51,490 INFO L263 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-18 22:43:51,491 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:43:51,602 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-18 22:43:51,603 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-18 22:43:51,603 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:43:51,603 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1447324421] [2022-03-18 22:43:51,603 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:43:51,603 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [105529566] [2022-03-18 22:43:51,603 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [105529566] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 22:43:51,604 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 22:43:51,604 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-18 22:43:51,604 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1385151590] [2022-03-18 22:43:51,604 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 22:43:51,604 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 22:43:51,604 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:43:51,605 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 22:43:51,605 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-18 22:43:51,605 INFO L87 Difference]: Start difference. First operand 38 states and 46 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-18 22:43:51,631 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:43:51,631 INFO L93 Difference]: Finished difference Result 51 states and 63 transitions. [2022-03-18 22:43:51,632 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 22:43:51,632 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 39 [2022-03-18 22:43:51,632 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:43:51,633 INFO L225 Difference]: With dead ends: 51 [2022-03-18 22:43:51,633 INFO L226 Difference]: Without dead ends: 49 [2022-03-18 22:43:51,633 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-18 22:43:51,634 INFO L912 BasicCegarLoop]: 43 mSDtfsCounter, 7 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 22:43:51,634 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 153 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 22:43:51,635 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2022-03-18 22:43:51,640 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2022-03-18 22:43:51,640 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 26 states have (on average 1.1538461538461537) internal successors, (30), 27 states have internal predecessors, (30), 16 states have call successors, (16), 6 states have call predecessors, (16), 5 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-18 22:43:51,641 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 60 transitions. [2022-03-18 22:43:51,641 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 60 transitions. Word has length 39 [2022-03-18 22:43:51,642 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:43:51,642 INFO L478 AbstractCegarLoop]: Abstraction has 48 states and 60 transitions. [2022-03-18 22:43:51,642 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-18 22:43:51,642 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 60 transitions. [2022-03-18 22:43:51,644 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-03-18 22:43:51,644 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:43:51,645 INFO L500 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] [2022-03-18 22:43:51,665 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-18 22:43:51,861 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:51,861 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:43:51,861 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:43:51,862 INFO L85 PathProgramCache]: Analyzing trace with hash -2010982190, now seen corresponding path program 1 times [2022-03-18 22:43:51,862 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:43:51,862 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1150091707] [2022-03-18 22:43:51,862 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:51,862 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:43:51,869 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:43:51,869 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [887756114] [2022-03-18 22:43:51,869 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:51,869 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:51,870 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:43:51,878 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:43:51,880 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-18 22:43:51,916 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:51,916 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-18 22:43:51,921 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:43:52,118 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 7 proven. 6 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-03-18 22:43:52,118 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:43:52,199 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:43:52,199 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1150091707] [2022-03-18 22:43:52,199 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:43:52,199 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [887756114] [2022-03-18 22:43:52,199 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [887756114] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-18 22:43:52,199 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-18 22:43:52,199 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-03-18 22:43:52,200 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1839702821] [2022-03-18 22:43:52,200 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-18 22:43:52,200 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-18 22:43:52,200 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:43:52,200 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-18 22:43:52,201 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-03-18 22:43:52,201 INFO L87 Difference]: Start difference. First operand 48 states and 60 transitions. Second operand has 8 states, 8 states have (on average 2.375) internal successors, (19), 6 states have internal predecessors, (19), 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) [2022-03-18 22:43:52,285 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:43:52,285 INFO L93 Difference]: Finished difference Result 55 states and 66 transitions. [2022-03-18 22:43:52,285 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-18 22:43:52,285 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.375) internal successors, (19), 6 states have internal predecessors, (19), 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 44 [2022-03-18 22:43:52,286 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:43:52,286 INFO L225 Difference]: With dead ends: 55 [2022-03-18 22:43:52,286 INFO L226 Difference]: Without dead ends: 53 [2022-03-18 22:43:52,287 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 40 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-03-18 22:43:52,287 INFO L912 BasicCegarLoop]: 35 mSDtfsCounter, 22 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 94 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 176 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 94 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 22:43:52,287 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 176 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 94 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 22:43:52,288 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2022-03-18 22:43:52,300 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 52. [2022-03-18 22:43:52,300 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 30 states have internal predecessors, (33), 16 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-18 22:43:52,301 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 63 transitions. [2022-03-18 22:43:52,301 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 63 transitions. Word has length 44 [2022-03-18 22:43:52,301 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:43:52,302 INFO L478 AbstractCegarLoop]: Abstraction has 52 states and 63 transitions. [2022-03-18 22:43:52,302 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.375) internal successors, (19), 6 states have internal predecessors, (19), 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) [2022-03-18 22:43:52,303 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 63 transitions. [2022-03-18 22:43:52,304 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2022-03-18 22:43:52,304 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:43:52,304 INFO L500 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] [2022-03-18 22:43:52,341 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-18 22:43:52,521 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:52,521 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:43:52,521 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:43:52,522 INFO L85 PathProgramCache]: Analyzing trace with hash 2061823606, now seen corresponding path program 1 times [2022-03-18 22:43:52,522 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:43:52,522 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2136390519] [2022-03-18 22:43:52,522 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:52,522 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:43:52,541 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:43:52,541 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1666871386] [2022-03-18 22:43:52,541 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:52,541 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:52,541 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:43:52,550 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:43:52,552 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-18 22:43:52,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:52,586 INFO L263 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 23 conjunts are in the unsatisfiable core [2022-03-18 22:43:52,588 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:43:52,736 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-03-18 22:43:52,737 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:43:52,801 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:43:52,802 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2136390519] [2022-03-18 22:43:52,802 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:43:52,802 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1666871386] [2022-03-18 22:43:52,802 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1666871386] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-18 22:43:52,802 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-18 22:43:52,802 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-03-18 22:43:52,802 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1328308966] [2022-03-18 22:43:52,802 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-18 22:43:52,803 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-18 22:43:52,803 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:43:52,803 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-18 22:43:52,803 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2022-03-18 22:43:52,803 INFO L87 Difference]: Start difference. First operand 52 states and 63 transitions. Second operand has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 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) [2022-03-18 22:43:52,883 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:43:52,883 INFO L93 Difference]: Finished difference Result 59 states and 69 transitions. [2022-03-18 22:43:52,884 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-18 22:43:52,884 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 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 49 [2022-03-18 22:43:52,884 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:43:52,884 INFO L225 Difference]: With dead ends: 59 [2022-03-18 22:43:52,885 INFO L226 Difference]: Without dead ends: 57 [2022-03-18 22:43:52,885 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 45 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2022-03-18 22:43:52,885 INFO L912 BasicCegarLoop]: 31 mSDtfsCounter, 12 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 89 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 92 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 89 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 22:43:52,886 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 130 Invalid, 92 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 89 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 22:43:52,886 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2022-03-18 22:43:52,890 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 56. [2022-03-18 22:43:52,890 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 32 states have (on average 1.125) internal successors, (36), 33 states have internal predecessors, (36), 16 states have call successors, (16), 8 states have call predecessors, (16), 7 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-18 22:43:52,891 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 66 transitions. [2022-03-18 22:43:52,891 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 66 transitions. Word has length 49 [2022-03-18 22:43:52,891 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:43:52,891 INFO L478 AbstractCegarLoop]: Abstraction has 56 states and 66 transitions. [2022-03-18 22:43:52,891 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 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) [2022-03-18 22:43:52,891 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 66 transitions. [2022-03-18 22:43:52,892 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-03-18 22:43:52,892 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:43:52,892 INFO L500 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 22:43:52,931 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-18 22:43:53,110 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:53,110 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:43:53,111 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:43:53,111 INFO L85 PathProgramCache]: Analyzing trace with hash 1928289951, now seen corresponding path program 1 times [2022-03-18 22:43:53,111 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:43:53,111 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2050774207] [2022-03-18 22:43:53,111 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:53,111 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:43:53,128 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:43:53,129 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [699583193] [2022-03-18 22:43:53,132 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:53,132 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:53,132 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:43:53,151 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:43:53,152 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-18 22:43:53,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:53,192 INFO L263 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-18 22:43:53,196 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:43:53,303 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2022-03-18 22:43:53,303 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:43:53,433 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2022-03-18 22:43:53,433 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:43:53,433 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2050774207] [2022-03-18 22:43:53,433 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:43:53,434 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [699583193] [2022-03-18 22:43:53,434 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [699583193] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 22:43:53,434 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 22:43:53,434 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-03-18 22:43:53,434 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [683195354] [2022-03-18 22:43:53,434 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 22:43:53,434 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-18 22:43:53,434 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:43:53,435 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-18 22:43:53,435 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-03-18 22:43:53,435 INFO L87 Difference]: Start difference. First operand 56 states and 66 transitions. Second operand has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2022-03-18 22:43:53,562 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:43:53,562 INFO L93 Difference]: Finished difference Result 103 states and 141 transitions. [2022-03-18 22:43:53,562 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-18 22:43:53,563 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 58 [2022-03-18 22:43:53,563 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:43:53,564 INFO L225 Difference]: With dead ends: 103 [2022-03-18 22:43:53,564 INFO L226 Difference]: Without dead ends: 95 [2022-03-18 22:43:53,564 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 107 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2022-03-18 22:43:53,564 INFO L912 BasicCegarLoop]: 57 mSDtfsCounter, 30 mSDsluCounter, 310 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 367 SdHoareTripleChecker+Invalid, 151 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 22:43:53,565 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 367 Invalid, 151 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 22:43:53,565 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2022-03-18 22:43:53,573 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 86. [2022-03-18 22:43:53,573 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 46 states have (on average 1.1956521739130435) internal successors, (55), 47 states have internal predecessors, (55), 32 states have call successors, (32), 8 states have call predecessors, (32), 7 states have return successors, (30), 30 states have call predecessors, (30), 30 states have call successors, (30) [2022-03-18 22:43:53,574 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 117 transitions. [2022-03-18 22:43:53,574 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 117 transitions. Word has length 58 [2022-03-18 22:43:53,574 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:43:53,575 INFO L478 AbstractCegarLoop]: Abstraction has 86 states and 117 transitions. [2022-03-18 22:43:53,575 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2022-03-18 22:43:53,575 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 117 transitions. [2022-03-18 22:43:53,575 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2022-03-18 22:43:53,575 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:43:53,576 INFO L500 BasicCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 22:43:53,605 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2022-03-18 22:43:53,791 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:53,792 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:43:53,792 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:43:53,792 INFO L85 PathProgramCache]: Analyzing trace with hash -1649820922, now seen corresponding path program 1 times [2022-03-18 22:43:53,792 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:43:53,792 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1167690360] [2022-03-18 22:43:53,792 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:53,792 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:43:53,799 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:43:53,799 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [275931692] [2022-03-18 22:43:53,799 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:53,799 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:53,800 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:43:53,800 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:43:53,801 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-18 22:43:53,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:53,840 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 30 conjunts are in the unsatisfiable core [2022-03-18 22:43:53,842 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:43:54,075 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 15 proven. 12 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-03-18 22:43:54,075 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:43:54,242 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-03-18 22:43:54,242 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:43:54,242 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1167690360] [2022-03-18 22:43:54,242 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:43:54,242 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [275931692] [2022-03-18 22:43:54,242 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [275931692] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 22:43:54,243 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 22:43:54,243 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-03-18 22:43:54,243 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1025373399] [2022-03-18 22:43:54,243 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 22:43:54,243 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-18 22:43:54,243 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:43:54,244 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-18 22:43:54,244 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2022-03-18 22:43:54,244 INFO L87 Difference]: Start difference. First operand 86 states and 117 transitions. Second operand has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 11 states have internal predecessors, (35), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (17), 6 states have call predecessors, (17), 6 states have call successors, (17) [2022-03-18 22:43:54,504 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:43:54,504 INFO L93 Difference]: Finished difference Result 129 states and 182 transitions. [2022-03-18 22:43:54,504 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-18 22:43:54,504 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 11 states have internal predecessors, (35), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (17), 6 states have call predecessors, (17), 6 states have call successors, (17) Word has length 64 [2022-03-18 22:43:54,505 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:43:54,506 INFO L225 Difference]: With dead ends: 129 [2022-03-18 22:43:54,507 INFO L226 Difference]: Without dead ends: 125 [2022-03-18 22:43:54,507 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 120 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=65, Invalid=241, Unknown=0, NotChecked=0, Total=306 [2022-03-18 22:43:54,507 INFO L912 BasicCegarLoop]: 41 mSDtfsCounter, 38 mSDsluCounter, 200 mSDsCounter, 0 mSdLazyCounter, 215 mSolverCounterSat, 64 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 241 SdHoareTripleChecker+Invalid, 279 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 64 IncrementalHoareTripleChecker+Valid, 215 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-18 22:43:54,508 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 241 Invalid, 279 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [64 Valid, 215 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-18 22:43:54,508 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2022-03-18 22:43:54,518 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 93. [2022-03-18 22:43:54,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 50 states have (on average 1.18) internal successors, (59), 52 states have internal predecessors, (59), 34 states have call successors, (34), 9 states have call predecessors, (34), 8 states have return successors, (32), 31 states have call predecessors, (32), 32 states have call successors, (32) [2022-03-18 22:43:54,520 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 125 transitions. [2022-03-18 22:43:54,520 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 125 transitions. Word has length 64 [2022-03-18 22:43:54,520 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:43:54,520 INFO L478 AbstractCegarLoop]: Abstraction has 93 states and 125 transitions. [2022-03-18 22:43:54,520 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 11 states have internal predecessors, (35), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (17), 6 states have call predecessors, (17), 6 states have call successors, (17) [2022-03-18 22:43:54,520 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 125 transitions. [2022-03-18 22:43:54,521 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2022-03-18 22:43:54,521 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:43:54,521 INFO L500 BasicCegarLoop]: trace histogram [7, 6, 6, 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] [2022-03-18 22:43:54,553 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-03-18 22:43:54,738 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:54,738 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:43:54,738 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:43:54,739 INFO L85 PathProgramCache]: Analyzing trace with hash -385302302, now seen corresponding path program 2 times [2022-03-18 22:43:54,739 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:43:54,739 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [86683375] [2022-03-18 22:43:54,739 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:54,739 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:43:54,745 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:43:54,746 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1303615863] [2022-03-18 22:43:54,746 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-18 22:43:54,746 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:54,746 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:43:54,747 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:43:54,751 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-18 22:43:54,804 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-18 22:43:54,804 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 22:43:54,805 INFO L263 TraceCheckSpWp]: Trace formula consists of 195 conjuncts, 35 conjunts are in the unsatisfiable core [2022-03-18 22:43:54,807 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:43:55,157 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2022-03-18 22:43:55,157 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:43:55,343 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-03-18 22:43:55,343 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:43:55,343 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [86683375] [2022-03-18 22:43:55,343 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:43:55,343 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1303615863] [2022-03-18 22:43:55,343 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1303615863] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 22:43:55,343 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 22:43:55,343 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 15 [2022-03-18 22:43:55,344 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [469294518] [2022-03-18 22:43:55,344 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 22:43:55,344 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-18 22:43:55,344 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:43:55,344 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-18 22:43:55,344 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=170, Unknown=0, NotChecked=0, Total=210 [2022-03-18 22:43:55,345 INFO L87 Difference]: Start difference. First operand 93 states and 125 transitions. Second operand has 15 states, 15 states have (on average 2.2) internal successors, (33), 13 states have internal predecessors, (33), 8 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (21), 8 states have call predecessors, (21), 8 states have call successors, (21) [2022-03-18 22:43:58,094 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:43:58,095 INFO L93 Difference]: Finished difference Result 229 states and 335 transitions. [2022-03-18 22:43:58,095 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2022-03-18 22:43:58,095 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.2) internal successors, (33), 13 states have internal predecessors, (33), 8 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (21), 8 states have call predecessors, (21), 8 states have call successors, (21) Word has length 69 [2022-03-18 22:43:58,095 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:43:58,097 INFO L225 Difference]: With dead ends: 229 [2022-03-18 22:43:58,097 INFO L226 Difference]: Without dead ends: 227 [2022-03-18 22:43:58,097 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 123 SyntacticMatches, 1 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 208 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=225, Invalid=767, Unknown=0, NotChecked=0, Total=992 [2022-03-18 22:43:58,098 INFO L912 BasicCegarLoop]: 58 mSDtfsCounter, 91 mSDsluCounter, 375 mSDsCounter, 0 mSdLazyCounter, 424 mSolverCounterSat, 157 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 95 SdHoareTripleChecker+Valid, 433 SdHoareTripleChecker+Invalid, 581 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 157 IncrementalHoareTripleChecker+Valid, 424 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2022-03-18 22:43:58,098 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [95 Valid, 433 Invalid, 581 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [157 Valid, 424 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2022-03-18 22:43:58,099 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 227 states. [2022-03-18 22:43:58,121 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 227 to 178. [2022-03-18 22:43:58,121 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 178 states, 97 states have (on average 1.2164948453608246) internal successors, (118), 100 states have internal predecessors, (118), 69 states have call successors, (69), 12 states have call predecessors, (69), 11 states have return successors, (67), 65 states have call predecessors, (67), 67 states have call successors, (67) [2022-03-18 22:43:58,146 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 178 states to 178 states and 254 transitions. [2022-03-18 22:43:58,147 INFO L78 Accepts]: Start accepts. Automaton has 178 states and 254 transitions. Word has length 69 [2022-03-18 22:43:58,147 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:43:58,147 INFO L478 AbstractCegarLoop]: Abstraction has 178 states and 254 transitions. [2022-03-18 22:43:58,147 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.2) internal successors, (33), 13 states have internal predecessors, (33), 8 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (21), 8 states have call predecessors, (21), 8 states have call successors, (21) [2022-03-18 22:43:58,147 INFO L276 IsEmpty]: Start isEmpty. Operand 178 states and 254 transitions. [2022-03-18 22:43:58,148 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2022-03-18 22:43:58,148 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:43:58,148 INFO L500 BasicCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 22:43:58,166 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-18 22:43:58,367 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-03-18 22:43:58,367 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:43:58,368 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:43:58,368 INFO L85 PathProgramCache]: Analyzing trace with hash -524447642, now seen corresponding path program 3 times [2022-03-18 22:43:58,368 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:43:58,368 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1878979579] [2022-03-18 22:43:58,368 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:58,368 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:43:58,384 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:43:58,384 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1852784570] [2022-03-18 22:43:58,384 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-18 22:43:58,384 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:58,384 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:43:58,385 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:43:58,386 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-03-18 22:43:58,425 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-03-18 22:43:58,425 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 22:43:58,426 INFO L263 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 38 conjunts are in the unsatisfiable core [2022-03-18 22:43:58,428 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:43:58,840 INFO L134 CoverageAnalysis]: Checked inductivity of 129 backedges. 31 proven. 8 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2022-03-18 22:43:58,840 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:43:58,950 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:43:58,951 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1878979579] [2022-03-18 22:43:58,951 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:43:58,951 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1852784570] [2022-03-18 22:43:58,951 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1852784570] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-18 22:43:58,951 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-18 22:43:58,951 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-03-18 22:43:58,951 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1829831758] [2022-03-18 22:43:58,951 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-18 22:43:58,951 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-18 22:43:58,952 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:43:58,952 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-18 22:43:58,952 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2022-03-18 22:43:58,952 INFO L87 Difference]: Start difference. First operand 178 states and 254 transitions. Second operand has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 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) [2022-03-18 22:43:59,165 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:43:59,166 INFO L93 Difference]: Finished difference Result 210 states and 293 transitions. [2022-03-18 22:43:59,166 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-18 22:43:59,166 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 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 [2022-03-18 22:43:59,167 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:43:59,168 INFO L225 Difference]: With dead ends: 210 [2022-03-18 22:43:59,168 INFO L226 Difference]: Without dead ends: 208 [2022-03-18 22:43:59,169 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 67 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=42, Invalid=168, Unknown=0, NotChecked=0, Total=210 [2022-03-18 22:43:59,169 INFO L912 BasicCegarLoop]: 38 mSDtfsCounter, 21 mSDsluCounter, 214 mSDsCounter, 0 mSdLazyCounter, 242 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 252 SdHoareTripleChecker+Invalid, 257 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 242 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-18 22:43:59,169 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 252 Invalid, 257 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 242 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-18 22:43:59,170 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 208 states. [2022-03-18 22:43:59,191 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 208 to 205. [2022-03-18 22:43:59,191 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 205 states, 113 states have (on average 1.2035398230088497) internal successors, (136), 116 states have internal predecessors, (136), 77 states have call successors, (77), 15 states have call predecessors, (77), 14 states have return successors, (75), 73 states have call predecessors, (75), 75 states have call successors, (75) [2022-03-18 22:43:59,192 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 205 states to 205 states and 288 transitions. [2022-03-18 22:43:59,193 INFO L78 Accepts]: Start accepts. Automaton has 205 states and 288 transitions. Word has length 74 [2022-03-18 22:43:59,193 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:43:59,193 INFO L478 AbstractCegarLoop]: Abstraction has 205 states and 288 transitions. [2022-03-18 22:43:59,193 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 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) [2022-03-18 22:43:59,193 INFO L276 IsEmpty]: Start isEmpty. Operand 205 states and 288 transitions. [2022-03-18 22:43:59,194 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2022-03-18 22:43:59,194 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:43:59,194 INFO L500 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 22:43:59,211 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-03-18 22:43:59,411 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-03-18 22:43:59,411 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:43:59,411 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:43:59,412 INFO L85 PathProgramCache]: Analyzing trace with hash -1568721063, now seen corresponding path program 1 times [2022-03-18 22:43:59,412 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:43:59,412 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1171072566] [2022-03-18 22:43:59,412 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:59,412 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:43:59,418 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:43:59,418 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1210490704] [2022-03-18 22:43:59,418 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:43:59,418 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:43:59,418 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:43:59,426 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:43:59,435 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-03-18 22:43:59,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:43:59,492 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 40 conjunts are in the unsatisfiable core [2022-03-18 22:43:59,495 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:43:59,963 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 33 proven. 12 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2022-03-18 22:43:59,963 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:44:00,463 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 33 proven. 12 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2022-03-18 22:44:00,463 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:44:00,463 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1171072566] [2022-03-18 22:44:00,463 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:44:00,463 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1210490704] [2022-03-18 22:44:00,463 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1210490704] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 22:44:00,463 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 22:44:00,464 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2022-03-18 22:44:00,464 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1952346142] [2022-03-18 22:44:00,464 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 22:44:00,464 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-03-18 22:44:00,464 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:44:00,465 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-03-18 22:44:00,465 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=284, Unknown=0, NotChecked=0, Total=342 [2022-03-18 22:44:00,465 INFO L87 Difference]: Start difference. First operand 205 states and 288 transitions. Second operand has 19 states, 17 states have (on average 2.176470588235294) internal successors, (37), 18 states have internal predecessors, (37), 11 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (23), 9 states have call predecessors, (23), 9 states have call successors, (23) [2022-03-18 22:44:02,581 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:44:02,582 INFO L93 Difference]: Finished difference Result 307 states and 440 transitions. [2022-03-18 22:44:02,582 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2022-03-18 22:44:02,582 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 2.176470588235294) internal successors, (37), 18 states have internal predecessors, (37), 11 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (23), 9 states have call predecessors, (23), 9 states have call successors, (23) Word has length 80 [2022-03-18 22:44:02,583 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:44:02,587 INFO L225 Difference]: With dead ends: 307 [2022-03-18 22:44:02,587 INFO L226 Difference]: Without dead ends: 298 [2022-03-18 22:44:02,588 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 141 SyntacticMatches, 1 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 155 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=222, Invalid=1038, Unknown=0, NotChecked=0, Total=1260 [2022-03-18 22:44:02,588 INFO L912 BasicCegarLoop]: 43 mSDtfsCounter, 62 mSDsluCounter, 399 mSDsCounter, 0 mSdLazyCounter, 633 mSolverCounterSat, 144 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 442 SdHoareTripleChecker+Invalid, 777 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 144 IncrementalHoareTripleChecker+Valid, 633 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2022-03-18 22:44:02,588 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [64 Valid, 442 Invalid, 777 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [144 Valid, 633 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2022-03-18 22:44:02,589 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 298 states. [2022-03-18 22:44:02,654 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 298 to 295. [2022-03-18 22:44:02,655 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 295 states, 164 states have (on average 1.2073170731707317) internal successors, (198), 167 states have internal predecessors, (198), 113 states have call successors, (113), 18 states have call predecessors, (113), 17 states have return successors, (111), 109 states have call predecessors, (111), 111 states have call successors, (111) [2022-03-18 22:44:02,658 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 295 states to 295 states and 422 transitions. [2022-03-18 22:44:02,658 INFO L78 Accepts]: Start accepts. Automaton has 295 states and 422 transitions. Word has length 80 [2022-03-18 22:44:02,658 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:44:02,659 INFO L478 AbstractCegarLoop]: Abstraction has 295 states and 422 transitions. [2022-03-18 22:44:02,659 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 2.176470588235294) internal successors, (37), 18 states have internal predecessors, (37), 11 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (23), 9 states have call predecessors, (23), 9 states have call successors, (23) [2022-03-18 22:44:02,659 INFO L276 IsEmpty]: Start isEmpty. Operand 295 states and 422 transitions. [2022-03-18 22:44:02,661 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2022-03-18 22:44:02,661 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:44:02,661 INFO L500 BasicCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 22:44:02,679 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-03-18 22:44:02,881 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-03-18 22:44:02,881 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:44:02,882 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:44:02,882 INFO L85 PathProgramCache]: Analyzing trace with hash 17347872, now seen corresponding path program 1 times [2022-03-18 22:44:02,882 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:44:02,882 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1205123148] [2022-03-18 22:44:02,882 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:44:02,882 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:44:02,889 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:44:02,889 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [16081155] [2022-03-18 22:44:02,889 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:44:02,889 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:44:02,889 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:44:02,890 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:44:02,891 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-03-18 22:44:02,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 22:44:02,962 INFO L263 TraceCheckSpWp]: Trace formula consists of 246 conjuncts, 54 conjunts are in the unsatisfiable core [2022-03-18 22:44:02,964 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:44:03,626 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 55 proven. 57 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2022-03-18 22:44:03,626 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:44:11,490 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 55 proven. 57 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2022-03-18 22:44:11,490 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:44:11,490 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1205123148] [2022-03-18 22:44:11,490 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:44:11,490 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [16081155] [2022-03-18 22:44:11,490 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [16081155] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 22:44:11,490 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 22:44:11,490 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 13] total 19 [2022-03-18 22:44:11,490 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [245419008] [2022-03-18 22:44:11,491 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 22:44:11,491 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-03-18 22:44:11,491 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:44:11,491 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-03-18 22:44:11,491 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=263, Unknown=2, NotChecked=0, Total=342 [2022-03-18 22:44:11,491 INFO L87 Difference]: Start difference. First operand 295 states and 422 transitions. Second operand has 19 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 13 states have call successors, (32), 2 states have call predecessors, (32), 2 states have return successors, (29), 11 states have call predecessors, (29), 12 states have call successors, (29) [2022-03-18 22:44:26,149 WARN L232 SmtUtils]: Spent 7.40s on a formula simplification that was a NOOP. DAG size: 90 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:44:28,212 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:44:34,276 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.27s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:44:49,390 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:44:52,235 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:44:54,239 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:44:56,241 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:44:58,082 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.82s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:45:01,064 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:45:03,192 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:45:06,199 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:45:08,397 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.32s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:45:12,255 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:45:12,255 INFO L93 Difference]: Finished difference Result 343 states and 495 transitions. [2022-03-18 22:45:12,256 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-03-18 22:45:12,256 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 13 states have call successors, (32), 2 states have call predecessors, (32), 2 states have return successors, (29), 11 states have call predecessors, (29), 12 states have call successors, (29) Word has length 96 [2022-03-18 22:45:12,256 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:45:12,258 INFO L225 Difference]: With dead ends: 343 [2022-03-18 22:45:12,258 INFO L226 Difference]: Without dead ends: 341 [2022-03-18 22:45:12,259 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 174 SyntacticMatches, 2 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 190 ImplicationChecksByTransitivity, 39.5s TimeCoverageRelationStatistics Valid=220, Invalid=703, Unknown=7, NotChecked=0, Total=930 [2022-03-18 22:45:12,259 INFO L912 BasicCegarLoop]: 38 mSDtfsCounter, 79 mSDsluCounter, 274 mSDsCounter, 0 mSdLazyCounter, 426 mSolverCounterSat, 131 mSolverCounterUnsat, 8 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 28.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 91 SdHoareTripleChecker+Valid, 312 SdHoareTripleChecker+Invalid, 565 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 131 IncrementalHoareTripleChecker+Valid, 426 IncrementalHoareTripleChecker+Invalid, 8 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 28.4s IncrementalHoareTripleChecker+Time [2022-03-18 22:45:12,259 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [91 Valid, 312 Invalid, 565 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [131 Valid, 426 Invalid, 8 Unknown, 0 Unchecked, 28.4s Time] [2022-03-18 22:45:12,259 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 341 states. [2022-03-18 22:45:12,316 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 341 to 336. [2022-03-18 22:45:12,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 336 states, 183 states have (on average 1.2131147540983607) internal successors, (222), 189 states have internal predecessors, (222), 134 states have call successors, (134), 19 states have call predecessors, (134), 18 states have return successors, (132), 127 states have call predecessors, (132), 132 states have call successors, (132) [2022-03-18 22:45:12,319 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 336 states to 336 states and 488 transitions. [2022-03-18 22:45:12,319 INFO L78 Accepts]: Start accepts. Automaton has 336 states and 488 transitions. Word has length 96 [2022-03-18 22:45:12,319 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:45:12,319 INFO L478 AbstractCegarLoop]: Abstraction has 336 states and 488 transitions. [2022-03-18 22:45:12,319 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 13 states have call successors, (32), 2 states have call predecessors, (32), 2 states have return successors, (29), 11 states have call predecessors, (29), 12 states have call successors, (29) [2022-03-18 22:45:12,319 INFO L276 IsEmpty]: Start isEmpty. Operand 336 states and 488 transitions. [2022-03-18 22:45:12,320 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2022-03-18 22:45:12,320 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:45:12,320 INFO L500 BasicCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 22:45:12,340 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-03-18 22:45:12,520 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-03-18 22:45:12,521 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:45:12,521 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:45:12,521 INFO L85 PathProgramCache]: Analyzing trace with hash -1494614922, now seen corresponding path program 4 times [2022-03-18 22:45:12,521 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:45:12,521 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1654767785] [2022-03-18 22:45:12,521 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:45:12,521 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:45:12,527 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:45:12,527 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [765923266] [2022-03-18 22:45:12,527 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-18 22:45:12,527 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:45:12,527 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:45:12,540 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:45:12,542 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-03-18 22:45:12,585 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-18 22:45:12,585 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 22:45:12,586 INFO L263 TraceCheckSpWp]: Trace formula consists of 223 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-18 22:45:12,587 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:45:12,700 INFO L134 CoverageAnalysis]: Checked inductivity of 289 backedges. 135 proven. 0 refuted. 0 times theorem prover too weak. 154 trivial. 0 not checked. [2022-03-18 22:45:12,700 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-18 22:45:12,700 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:45:12,700 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1654767785] [2022-03-18 22:45:12,700 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:45:12,700 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [765923266] [2022-03-18 22:45:12,700 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [765923266] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 22:45:12,700 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 22:45:12,701 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-18 22:45:12,701 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1466182343] [2022-03-18 22:45:12,701 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 22:45:12,701 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 22:45:12,701 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:45:12,701 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 22:45:12,701 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-18 22:45:12,701 INFO L87 Difference]: Start difference. First operand 336 states and 488 transitions. Second operand has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 3 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2022-03-18 22:45:12,779 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:45:12,779 INFO L93 Difference]: Finished difference Result 410 states and 590 transitions. [2022-03-18 22:45:12,780 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-18 22:45:12,780 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 3 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) Word has length 99 [2022-03-18 22:45:12,780 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:45:12,781 INFO L225 Difference]: With dead ends: 410 [2022-03-18 22:45:12,781 INFO L226 Difference]: Without dead ends: 239 [2022-03-18 22:45:12,782 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 95 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2022-03-18 22:45:12,782 INFO L912 BasicCegarLoop]: 51 mSDtfsCounter, 6 mSDsluCounter, 112 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 22:45:12,783 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 163 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 22:45:12,783 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 239 states. [2022-03-18 22:45:12,886 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 239 to 215. [2022-03-18 22:45:12,886 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 215 states, 117 states have (on average 1.1367521367521367) internal successors, (133), 119 states have internal predecessors, (133), 79 states have call successors, (79), 19 states have call predecessors, (79), 18 states have return successors, (77), 76 states have call predecessors, (77), 77 states have call successors, (77) [2022-03-18 22:45:12,887 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 215 states to 215 states and 289 transitions. [2022-03-18 22:45:12,887 INFO L78 Accepts]: Start accepts. Automaton has 215 states and 289 transitions. Word has length 99 [2022-03-18 22:45:12,887 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:45:12,888 INFO L478 AbstractCegarLoop]: Abstraction has 215 states and 289 transitions. [2022-03-18 22:45:12,888 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 3 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2022-03-18 22:45:12,888 INFO L276 IsEmpty]: Start isEmpty. Operand 215 states and 289 transitions. [2022-03-18 22:45:12,888 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2022-03-18 22:45:12,889 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:45:12,889 INFO L500 BasicCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 22:45:12,910 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-03-18 22:45:13,108 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-03-18 22:45:13,108 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:45:13,108 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:45:13,109 INFO L85 PathProgramCache]: Analyzing trace with hash -527743528, now seen corresponding path program 2 times [2022-03-18 22:45:13,109 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:45:13,109 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [367473316] [2022-03-18 22:45:13,109 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:45:13,109 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:45:13,114 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:45:13,114 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [416701397] [2022-03-18 22:45:13,115 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-18 22:45:13,115 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:45:13,115 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:45:13,117 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:45:13,149 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-03-18 22:45:13,170 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-18 22:45:13,170 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 22:45:13,171 INFO L263 TraceCheckSpWp]: Trace formula consists of 295 conjuncts, 76 conjunts are in the unsatisfiable core [2022-03-18 22:45:13,173 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:45:13,875 INFO L134 CoverageAnalysis]: Checked inductivity of 453 backedges. 83 proven. 117 refuted. 0 times theorem prover too weak. 253 trivial. 0 not checked. [2022-03-18 22:45:13,875 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:45:14,157 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-18 22:45:14,340 INFO L134 CoverageAnalysis]: Checked inductivity of 453 backedges. 120 proven. 32 refuted. 0 times theorem prover too weak. 301 trivial. 0 not checked. [2022-03-18 22:45:14,340 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:45:14,340 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [367473316] [2022-03-18 22:45:14,340 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:45:14,340 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [416701397] [2022-03-18 22:45:14,340 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [416701397] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 22:45:14,340 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 22:45:14,340 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 10] total 21 [2022-03-18 22:45:14,340 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [277182410] [2022-03-18 22:45:14,340 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 22:45:14,341 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-03-18 22:45:14,341 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:45:14,341 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-03-18 22:45:14,341 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=341, Unknown=0, NotChecked=0, Total=420 [2022-03-18 22:45:14,341 INFO L87 Difference]: Start difference. First operand 215 states and 289 transitions. Second operand has 21 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 16 states have internal predecessors, (45), 14 states have call successors, (33), 2 states have call predecessors, (33), 2 states have return successors, (31), 13 states have call predecessors, (31), 14 states have call successors, (31) [2022-03-18 22:45:16,444 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:45:16,445 INFO L93 Difference]: Finished difference Result 246 states and 326 transitions. [2022-03-18 22:45:16,445 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2022-03-18 22:45:16,445 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 16 states have internal predecessors, (45), 14 states have call successors, (33), 2 states have call predecessors, (33), 2 states have return successors, (31), 13 states have call predecessors, (31), 14 states have call successors, (31) Word has length 116 [2022-03-18 22:45:16,445 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:45:16,449 INFO L225 Difference]: With dead ends: 246 [2022-03-18 22:45:16,449 INFO L226 Difference]: Without dead ends: 244 [2022-03-18 22:45:16,450 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 240 GetRequests, 211 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 158 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=158, Invalid=712, Unknown=0, NotChecked=0, Total=870 [2022-03-18 22:45:16,450 INFO L912 BasicCegarLoop]: 47 mSDtfsCounter, 42 mSDsluCounter, 434 mSDsCounter, 0 mSdLazyCounter, 585 mSolverCounterSat, 123 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 481 SdHoareTripleChecker+Invalid, 708 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 123 IncrementalHoareTripleChecker+Valid, 585 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2022-03-18 22:45:16,450 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [48 Valid, 481 Invalid, 708 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [123 Valid, 585 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2022-03-18 22:45:16,451 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 244 states. [2022-03-18 22:45:16,496 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 244 to 227. [2022-03-18 22:45:16,496 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 227 states, 126 states have (on average 1.126984126984127) internal successors, (142), 128 states have internal predecessors, (142), 79 states have call successors, (79), 22 states have call predecessors, (79), 21 states have return successors, (77), 76 states have call predecessors, (77), 77 states have call successors, (77) [2022-03-18 22:45:16,497 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 227 states to 227 states and 298 transitions. [2022-03-18 22:45:16,497 INFO L78 Accepts]: Start accepts. Automaton has 227 states and 298 transitions. Word has length 116 [2022-03-18 22:45:16,497 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:45:16,497 INFO L478 AbstractCegarLoop]: Abstraction has 227 states and 298 transitions. [2022-03-18 22:45:16,498 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 16 states have internal predecessors, (45), 14 states have call successors, (33), 2 states have call predecessors, (33), 2 states have return successors, (31), 13 states have call predecessors, (31), 14 states have call successors, (31) [2022-03-18 22:45:16,498 INFO L276 IsEmpty]: Start isEmpty. Operand 227 states and 298 transitions. [2022-03-18 22:45:16,498 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2022-03-18 22:45:16,499 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:45:16,499 INFO L500 BasicCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 22:45:16,520 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-03-18 22:45:16,714 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-03-18 22:45:16,715 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:45:16,715 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:45:16,715 INFO L85 PathProgramCache]: Analyzing trace with hash 1136073891, now seen corresponding path program 2 times [2022-03-18 22:45:16,715 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:45:16,715 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1969138462] [2022-03-18 22:45:16,715 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:45:16,715 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:45:16,721 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:45:16,721 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1728403377] [2022-03-18 22:45:16,721 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-18 22:45:16,721 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:45:16,721 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:45:16,722 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:45:16,723 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-03-18 22:45:16,779 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-18 22:45:16,779 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 22:45:16,781 INFO L263 TraceCheckSpWp]: Trace formula consists of 315 conjuncts, 76 conjunts are in the unsatisfiable core [2022-03-18 22:45:16,784 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:45:17,807 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-18 22:45:17,812 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-18 22:45:17,837 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-18 22:45:17,840 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-18 22:45:17,845 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-18 22:45:18,102 INFO L134 CoverageAnalysis]: Checked inductivity of 579 backedges. 133 proven. 86 refuted. 0 times theorem prover too weak. 360 trivial. 0 not checked. [2022-03-18 22:45:18,103 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:45:20,080 INFO L134 CoverageAnalysis]: Checked inductivity of 579 backedges. 154 proven. 12 refuted. 0 times theorem prover too weak. 413 trivial. 0 not checked. [2022-03-18 22:45:20,081 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:45:20,081 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1969138462] [2022-03-18 22:45:20,081 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:45:20,081 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1728403377] [2022-03-18 22:45:20,081 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1728403377] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 22:45:20,081 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 22:45:20,081 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 12] total 26 [2022-03-18 22:45:20,081 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [399916893] [2022-03-18 22:45:20,081 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 22:45:20,082 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-03-18 22:45:20,082 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:45:20,082 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-03-18 22:45:20,082 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=537, Unknown=0, NotChecked=0, Total=650 [2022-03-18 22:45:20,082 INFO L87 Difference]: Start difference. First operand 227 states and 298 transitions. Second operand has 26 states, 20 states have (on average 2.25) internal successors, (45), 19 states have internal predecessors, (45), 14 states have call successors, (33), 2 states have call predecessors, (33), 2 states have return successors, (31), 11 states have call predecessors, (31), 12 states have call successors, (31) [2022-03-18 22:45:28,962 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:45:28,962 INFO L93 Difference]: Finished difference Result 278 states and 365 transitions. [2022-03-18 22:45:28,963 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2022-03-18 22:45:28,963 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 20 states have (on average 2.25) internal successors, (45), 19 states have internal predecessors, (45), 14 states have call successors, (33), 2 states have call predecessors, (33), 2 states have return successors, (31), 11 states have call predecessors, (31), 12 states have call successors, (31) Word has length 127 [2022-03-18 22:45:28,963 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:45:28,964 INFO L225 Difference]: With dead ends: 278 [2022-03-18 22:45:28,964 INFO L226 Difference]: Without dead ends: 270 [2022-03-18 22:45:28,965 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 274 GetRequests, 228 SyntacticMatches, 1 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 458 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=383, Invalid=1779, Unknown=0, NotChecked=0, Total=2162 [2022-03-18 22:45:28,965 INFO L912 BasicCegarLoop]: 51 mSDtfsCounter, 70 mSDsluCounter, 257 mSDsCounter, 0 mSdLazyCounter, 781 mSolverCounterSat, 175 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 308 SdHoareTripleChecker+Invalid, 956 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 175 IncrementalHoareTripleChecker+Valid, 781 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.6s IncrementalHoareTripleChecker+Time [2022-03-18 22:45:28,965 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [77 Valid, 308 Invalid, 956 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [175 Valid, 781 Invalid, 0 Unknown, 0 Unchecked, 5.6s Time] [2022-03-18 22:45:28,966 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 270 states. [2022-03-18 22:45:29,010 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 270 to 235. [2022-03-18 22:45:29,010 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 235 states, 132 states have (on average 1.0909090909090908) internal successors, (144), 133 states have internal predecessors, (144), 78 states have call successors, (78), 25 states have call predecessors, (78), 24 states have return successors, (77), 76 states have call predecessors, (77), 77 states have call successors, (77) [2022-03-18 22:45:29,011 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 299 transitions. [2022-03-18 22:45:29,011 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 299 transitions. Word has length 127 [2022-03-18 22:45:29,011 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:45:29,011 INFO L478 AbstractCegarLoop]: Abstraction has 235 states and 299 transitions. [2022-03-18 22:45:29,012 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 20 states have (on average 2.25) internal successors, (45), 19 states have internal predecessors, (45), 14 states have call successors, (33), 2 states have call predecessors, (33), 2 states have return successors, (31), 11 states have call predecessors, (31), 12 states have call successors, (31) [2022-03-18 22:45:29,012 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 299 transitions. [2022-03-18 22:45:29,013 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 169 [2022-03-18 22:45:29,013 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:45:29,013 INFO L500 BasicCegarLoop]: trace histogram [24, 23, 23, 6, 6, 6, 6, 6, 6, 6, 6, 5, 4, 4, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 22:45:29,030 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-03-18 22:45:29,227 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:45:29,227 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:45:29,228 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:45:29,228 INFO L85 PathProgramCache]: Analyzing trace with hash -1033581786, now seen corresponding path program 3 times [2022-03-18 22:45:29,228 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:45:29,228 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [906860484] [2022-03-18 22:45:29,228 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:45:29,228 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:45:29,234 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:45:29,234 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [346739389] [2022-03-18 22:45:29,234 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-18 22:45:29,234 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:45:29,234 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:45:29,240 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:45:29,241 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-03-18 22:45:30,658 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-03-18 22:45:30,659 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 22:45:30,661 INFO L263 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 30 conjunts are in the unsatisfiable core [2022-03-18 22:45:30,687 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:45:36,338 INFO L134 CoverageAnalysis]: Checked inductivity of 1182 backedges. 168 proven. 35 refuted. 0 times theorem prover too weak. 979 trivial. 0 not checked. [2022-03-18 22:45:36,338 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:45:37,105 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:45:37,105 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [906860484] [2022-03-18 22:45:37,105 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:45:37,105 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [346739389] [2022-03-18 22:45:37,105 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [346739389] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-18 22:45:37,105 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-18 22:45:37,105 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2022-03-18 22:45:37,105 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [194463756] [2022-03-18 22:45:37,105 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-18 22:45:37,106 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-03-18 22:45:37,106 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:45:37,106 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-03-18 22:45:37,106 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=315, Unknown=0, NotChecked=0, Total=380 [2022-03-18 22:45:37,107 INFO L87 Difference]: Start difference. First operand 235 states and 299 transitions. Second operand has 17 states, 16 states have (on average 2.4375) internal successors, (39), 14 states have internal predecessors, (39), 8 states have call successors, (22), 2 states have call predecessors, (22), 3 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) [2022-03-18 22:45:43,716 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:45:43,717 INFO L93 Difference]: Finished difference Result 331 states and 450 transitions. [2022-03-18 22:45:43,717 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2022-03-18 22:45:43,717 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 2.4375) internal successors, (39), 14 states have internal predecessors, (39), 8 states have call successors, (22), 2 states have call predecessors, (22), 3 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) Word has length 168 [2022-03-18 22:45:43,717 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:45:43,718 INFO L225 Difference]: With dead ends: 331 [2022-03-18 22:45:43,718 INFO L226 Difference]: Without dead ends: 329 [2022-03-18 22:45:43,719 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 188 GetRequests, 153 SyntacticMatches, 1 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 238 ImplicationChecksByTransitivity, 7.7s TimeCoverageRelationStatistics Valid=218, Invalid=1042, Unknown=0, NotChecked=0, Total=1260 [2022-03-18 22:45:43,719 INFO L912 BasicCegarLoop]: 43 mSDtfsCounter, 46 mSDsluCounter, 255 mSDsCounter, 0 mSdLazyCounter, 531 mSolverCounterSat, 85 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 298 SdHoareTripleChecker+Invalid, 626 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 85 IncrementalHoareTripleChecker+Valid, 531 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 10 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2022-03-18 22:45:43,719 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [50 Valid, 298 Invalid, 626 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [85 Valid, 531 Invalid, 0 Unknown, 10 Unchecked, 2.1s Time] [2022-03-18 22:45:43,720 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 329 states. [2022-03-18 22:45:43,792 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 329 to 323. [2022-03-18 22:45:43,792 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 323 states, 170 states have (on average 1.1235294117647059) internal successors, (191), 172 states have internal predecessors, (191), 126 states have call successors, (126), 27 states have call predecessors, (126), 26 states have return successors, (125), 123 states have call predecessors, (125), 125 states have call successors, (125) [2022-03-18 22:45:43,793 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 323 states to 323 states and 442 transitions. [2022-03-18 22:45:43,794 INFO L78 Accepts]: Start accepts. Automaton has 323 states and 442 transitions. Word has length 168 [2022-03-18 22:45:43,794 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:45:43,794 INFO L478 AbstractCegarLoop]: Abstraction has 323 states and 442 transitions. [2022-03-18 22:45:43,794 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 2.4375) internal successors, (39), 14 states have internal predecessors, (39), 8 states have call successors, (22), 2 states have call predecessors, (22), 3 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) [2022-03-18 22:45:43,794 INFO L276 IsEmpty]: Start isEmpty. Operand 323 states and 442 transitions. [2022-03-18 22:45:43,796 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 191 [2022-03-18 22:45:43,796 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:45:43,796 INFO L500 BasicCegarLoop]: trace histogram [28, 27, 27, 7, 7, 7, 7, 7, 7, 7, 7, 6, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 22:45:43,802 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-03-18 22:45:44,001 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-03-18 22:45:44,001 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:45:44,001 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:45:44,002 INFO L85 PathProgramCache]: Analyzing trace with hash -44343328, now seen corresponding path program 4 times [2022-03-18 22:45:44,002 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:45:44,002 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [154646939] [2022-03-18 22:45:44,002 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:45:44,002 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:45:44,008 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:45:44,008 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1033659173] [2022-03-18 22:45:44,008 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-18 22:45:44,008 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:45:44,008 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:45:44,009 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:45:44,010 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-03-18 22:45:44,452 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-18 22:45:44,452 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 22:45:44,464 INFO L263 TraceCheckSpWp]: Trace formula consists of 407 conjuncts, 111 conjunts are in the unsatisfiable core [2022-03-18 22:45:44,467 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:45:46,891 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-18 22:46:11,403 WARN L232 SmtUtils]: Spent 5.27s on a formula simplification. DAG size of input: 9 DAG size of output: 1 (called from [L1067] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2022-03-18 22:46:13,578 INFO L134 CoverageAnalysis]: Checked inductivity of 1617 backedges. 303 proven. 264 refuted. 0 times theorem prover too weak. 1050 trivial. 0 not checked. [2022-03-18 22:46:13,578 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:46:35,001 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-18 22:46:35,007 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-18 22:47:42,185 INFO L134 CoverageAnalysis]: Checked inductivity of 1617 backedges. 356 proven. 91 refuted. 0 times theorem prover too weak. 1170 trivial. 0 not checked. [2022-03-18 22:47:42,186 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 22:47:42,186 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [154646939] [2022-03-18 22:47:42,186 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 22:47:42,186 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1033659173] [2022-03-18 22:47:42,186 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1033659173] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 22:47:42,186 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 22:47:42,186 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 17] total 34 [2022-03-18 22:47:42,186 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1484423785] [2022-03-18 22:47:42,186 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 22:47:42,187 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2022-03-18 22:47:42,187 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 22:47:42,187 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2022-03-18 22:47:42,187 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=260, Invalid=853, Unknown=9, NotChecked=0, Total=1122 [2022-03-18 22:47:42,188 INFO L87 Difference]: Start difference. First operand 323 states and 442 transitions. Second operand has 34 states, 32 states have (on average 1.96875) internal successors, (63), 28 states have internal predecessors, (63), 17 states have call successors, (56), 2 states have call predecessors, (56), 2 states have return successors, (54), 18 states have call predecessors, (54), 16 states have call successors, (54) [2022-03-18 22:47:44,893 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:47:51,863 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:48:17,558 WARN L232 SmtUtils]: Spent 22.97s on a formula simplification. DAG size of input: 103 DAG size of output: 102 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:48:56,365 WARN L232 SmtUtils]: Spent 36.45s on a formula simplification. DAG size of input: 130 DAG size of output: 129 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:49:08,967 WARN L232 SmtUtils]: Spent 9.82s on a formula simplification. DAG size of input: 87 DAG size of output: 86 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:49:22,418 WARN L232 SmtUtils]: Spent 12.68s on a formula simplification. DAG size of input: 104 DAG size of output: 103 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:49:24,431 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:49:26,446 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:49:36,395 WARN L232 SmtUtils]: Spent 9.53s on a formula simplification. DAG size of input: 86 DAG size of output: 85 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:49:51,930 WARN L232 SmtUtils]: Spent 15.25s on a formula simplification. DAG size of input: 85 DAG size of output: 84 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:49:54,626 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:49:56,646 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:50:05,482 WARN L232 SmtUtils]: Spent 8.58s on a formula simplification. DAG size of input: 86 DAG size of output: 85 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:50:32,593 WARN L232 SmtUtils]: Spent 26.52s on a formula simplification. DAG size of input: 103 DAG size of output: 102 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:50:40,666 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:50:58,468 WARN L232 SmtUtils]: Spent 17.41s on a formula simplification. DAG size of input: 110 DAG size of output: 109 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:51:10,741 WARN L232 SmtUtils]: Spent 11.98s on a formula simplification that was a NOOP. DAG size: 128 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:51:22,745 WARN L232 SmtUtils]: Spent 5.76s on a formula simplification that was a NOOP. DAG size: 86 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:51:37,143 WARN L232 SmtUtils]: Spent 10.81s on a formula simplification. DAG size of input: 80 DAG size of output: 79 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:51:39,269 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 22:51:42,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 22:51:42,870 INFO L93 Difference]: Finished difference Result 519 states and 725 transitions. [2022-03-18 22:51:42,870 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2022-03-18 22:51:42,870 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 32 states have (on average 1.96875) internal successors, (63), 28 states have internal predecessors, (63), 17 states have call successors, (56), 2 states have call predecessors, (56), 2 states have return successors, (54), 18 states have call predecessors, (54), 16 states have call successors, (54) Word has length 190 [2022-03-18 22:51:42,871 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 22:51:42,873 INFO L225 Difference]: With dead ends: 519 [2022-03-18 22:51:42,873 INFO L226 Difference]: Without dead ends: 517 [2022-03-18 22:51:42,874 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 425 GetRequests, 360 SyntacticMatches, 3 SemanticMatches, 62 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1053 ImplicationChecksByTransitivity, 265.6s TimeCoverageRelationStatistics Valid=1068, Invalid=2948, Unknown=16, NotChecked=0, Total=4032 [2022-03-18 22:51:42,874 INFO L912 BasicCegarLoop]: 59 mSDtfsCounter, 144 mSDsluCounter, 528 mSDsCounter, 0 mSdLazyCounter, 1130 mSolverCounterSat, 374 mSolverCounterUnsat, 8 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 23.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 155 SdHoareTripleChecker+Valid, 587 SdHoareTripleChecker+Invalid, 1584 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 374 IncrementalHoareTripleChecker+Valid, 1130 IncrementalHoareTripleChecker+Invalid, 8 IncrementalHoareTripleChecker+Unknown, 72 IncrementalHoareTripleChecker+Unchecked, 23.4s IncrementalHoareTripleChecker+Time [2022-03-18 22:51:42,875 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [155 Valid, 587 Invalid, 1584 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [374 Valid, 1130 Invalid, 8 Unknown, 72 Unchecked, 23.4s Time] [2022-03-18 22:51:42,875 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 517 states. [2022-03-18 22:51:43,100 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 517 to 497. [2022-03-18 22:51:43,101 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 497 states, 254 states have (on average 1.1377952755905512) internal successors, (289), 260 states have internal predecessors, (289), 206 states have call successors, (206), 37 states have call predecessors, (206), 36 states have return successors, (205), 199 states have call predecessors, (205), 205 states have call successors, (205) [2022-03-18 22:51:43,103 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 497 states to 497 states and 700 transitions. [2022-03-18 22:51:43,103 INFO L78 Accepts]: Start accepts. Automaton has 497 states and 700 transitions. Word has length 190 [2022-03-18 22:51:43,103 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 22:51:43,103 INFO L478 AbstractCegarLoop]: Abstraction has 497 states and 700 transitions. [2022-03-18 22:51:43,104 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 32 states have (on average 1.96875) internal successors, (63), 28 states have internal predecessors, (63), 17 states have call successors, (56), 2 states have call predecessors, (56), 2 states have return successors, (54), 18 states have call predecessors, (54), 16 states have call successors, (54) [2022-03-18 22:51:43,104 INFO L276 IsEmpty]: Start isEmpty. Operand 497 states and 700 transitions. [2022-03-18 22:51:43,119 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 235 [2022-03-18 22:51:43,119 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 22:51:43,120 INFO L500 BasicCegarLoop]: trace histogram [36, 35, 35, 9, 9, 9, 9, 9, 9, 9, 9, 8, 5, 4, 4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 22:51:43,128 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-03-18 22:51:43,325 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-03-18 22:51:43,326 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 22:51:43,326 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 22:51:43,326 INFO L85 PathProgramCache]: Analyzing trace with hash -690284640, now seen corresponding path program 5 times [2022-03-18 22:51:43,326 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 22:51:43,326 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1689650145] [2022-03-18 22:51:43,327 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 22:51:43,327 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 22:51:43,339 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 22:51:43,339 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1858440088] [2022-03-18 22:51:43,340 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-03-18 22:51:43,340 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 22:51:43,340 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 22:51:43,341 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 22:51:43,344 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-03-18 22:51:44,252 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2022-03-18 22:51:44,252 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 22:51:44,256 INFO L263 TraceCheckSpWp]: Trace formula consists of 530 conjuncts, 114 conjunts are in the unsatisfiable core [2022-03-18 22:51:44,260 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 22:51:47,111 INFO L134 CoverageAnalysis]: Checked inductivity of 2697 backedges. 299 proven. 444 refuted. 0 times theorem prover too weak. 1954 trivial. 0 not checked. [2022-03-18 22:51:47,111 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 22:52:51,480 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse7 (+ 3 c_main_~k~0))) (let ((.cse3 (+ (* (- 1) c_main_~q~0 .cse7) c_main_~p~0)) (.cse4 (+ c_main_~r~0 (* (- 1) (* c_main_~s~0 .cse7))))) (let ((.cse1 (* .cse4 c_main_~y~0)) (.cse2 (* c_main_~x~0 .cse3))) (let ((.cse0 (+ .cse1 .cse2)) (.cse5 (* c_main_~q~0 c_main_~x~0)) (.cse6 (* c_main_~s~0 c_main_~y~0))) (or (not (= .cse0 (+ c_main_~c~0 (* c_main_~b~0 (- 3))))) (= (+ .cse1 (* .cse0 c_main_~y~0) .cse2) (+ .cse1 (* c_main_~xy~0 .cse3) (* c_main_~yy~0 .cse4) .cse2)) (= .cse0 0) (not (= (+ .cse5 .cse6 (* c_main_~b~0 c_main_~y~0)) (+ (* c_main_~q~0 c_main_~xy~0) (* c_main_~yy~0 c_main_~s~0) c_main_~b~0))) (<= (+ c_main_~b~0 (* .cse5 3) (* c_main_~q~0 c_main_~x~0 c_main_~k~0) (* 3 .cse6) (* c_main_~s~0 c_main_~y~0 c_main_~k~0)) (+ (* c_main_~p~0 c_main_~x~0) (* c_main_~r~0 c_main_~y~0))) (not (<= (* c_main_~b~0 3) c_main_~c~0))))))) is different from true [2022-03-18 22:53:05,716 WARN L232 SmtUtils]: Spent 8.00s on a formula simplification that was a NOOP. DAG size: 60 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:53:31,845 WARN L232 SmtUtils]: Spent 16.13s on a formula simplification that was a NOOP. DAG size: 29 (called from [L1067] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2022-03-18 22:53:33,967 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse17 (* c_main_~s~0 c_main_~k~0)) (.cse16 (* (- 1) c_main_~q~0 c_main_~k~0))) (let ((.cse8 (+ c_main_~p~0 .cse16)) (.cse10 (+ c_main_~r~0 (* (- 1) .cse17))) (.cse14 (+ (* (- 3) c_main_~r~0) c_main_~s~0 (* 3 .cse17))) (.cse15 (+ (* (- 3) .cse16) (* c_main_~p~0 (- 3)) c_main_~q~0))) (let ((.cse12 (* .cse15 c_main_~x~0)) (.cse13 (* .cse14 c_main_~y~0)) (.cse7 (* .cse10 c_main_~y~0)) (.cse9 (* .cse8 c_main_~x~0))) (let ((.cse0 (+ .cse7 .cse9)) (.cse1 (* c_main_~p~0 c_main_~x~0)) (.cse2 (* c_main_~r~0 c_main_~y~0)) (.cse3 (* c_main_~q~0 c_main_~x~0)) (.cse5 (* c_main_~q~0 c_main_~x~0 c_main_~k~0)) (.cse4 (* c_main_~s~0 c_main_~y~0)) (.cse6 (* c_main_~s~0 c_main_~y~0 c_main_~k~0)) (.cse11 (+ .cse12 .cse13))) (or (not (= c_main_~c~0 .cse0)) (not (<= (+ (* 3 .cse1) (* 3 .cse2)) (+ .cse3 .cse4 (* .cse5 3) (* 3 .cse6)))) (not (= (+ .cse7 (* c_main_~xy~0 .cse8) .cse9 (* c_main_~yy~0 .cse10)) (+ .cse7 (* .cse0 c_main_~y~0) .cse9))) (= .cse11 0) (not (= c_main_~b~0 (+ .cse3 .cse4))) (<= (+ (* .cse1 4) (* .cse2 4)) (+ .cse3 (* .cse5 4) .cse4 (* .cse6 4))) (= (+ .cse12 .cse13 (* .cse11 c_main_~y~0)) (+ .cse12 .cse13 (* c_main_~yy~0 .cse14) (* c_main_~xy~0 .cse15)))))))) is different from true [2022-03-18 22:53:47,225 WARN L232 SmtUtils]: Spent 5.86s on a formula simplification that was a NOOP. DAG size: 19 (called from [L1067] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2022-03-18 22:54:41,716 WARN L232 SmtUtils]: Spent 19.75s on a formula simplification that was a NOOP. DAG size: 83 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 22:56:35,148 WARN L232 SmtUtils]: Spent 5.39s on a formula simplification that was a NOOP. DAG size: 31 (called from [L1067] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2022-03-18 22:56:37,158 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse18 (+ 2 c_main_~k~0))) (let ((.cse16 (* c_main_~s~0 .cse18)) (.cse17 (* (- 1) c_main_~q~0 .cse18))) (let ((.cse0 (+ c_main_~p~0 .cse17)) (.cse2 (+ (* (- 1) .cse16) c_main_~r~0)) (.cse14 (+ (* c_main_~p~0 (- 3)) c_main_~q~0 (* (- 3) .cse17))) (.cse15 (+ (* (- 3) c_main_~r~0) (* .cse16 3) c_main_~s~0))) (let ((.cse12 (* .cse15 c_main_~y~0)) (.cse13 (* .cse14 c_main_~x~0)) (.cse1 (* .cse2 c_main_~y~0)) (.cse3 (* .cse0 c_main_~x~0))) (let ((.cse4 (+ .cse1 .cse3)) (.cse5 (* c_main_~p~0 c_main_~x~0)) (.cse6 (* c_main_~r~0 c_main_~y~0)) (.cse9 (* c_main_~s~0 c_main_~y~0)) (.cse7 (* c_main_~q~0 c_main_~x~0)) (.cse8 (* c_main_~q~0 c_main_~x~0 c_main_~k~0)) (.cse10 (* c_main_~s~0 c_main_~y~0 c_main_~k~0)) (.cse11 (+ .cse12 .cse13))) (or (not (= (+ (* .cse0 c_main_~xy~0) .cse1 (* c_main_~yy~0 .cse2) .cse3) (+ (* .cse4 c_main_~y~0) .cse1 .cse3))) (not (= (+ c_main_~c~0 (* (- 2) c_main_~b~0)) .cse4)) (<= (+ (* .cse5 4) (* .cse6 4)) (+ (* .cse7 9) (* .cse8 4) (* 9 .cse9) (* .cse10 4))) (not (= c_main_~b~0 (+ .cse7 .cse9))) (= .cse11 0) (not (<= (+ (* 3 .cse5) (* 3 .cse6)) (+ (* 7 .cse9) (* 7 .cse7) (* .cse8 3) (* 3 .cse10)))) (= (+ (* .cse11 c_main_~y~0) .cse12 .cse13) (+ (* c_main_~xy~0 .cse14) (* c_main_~yy~0 .cse15) .cse12 .cse13)))))))) is different from true