/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 10:36:45,729 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 10:36:45,731 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 10:36:45,776 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 10:36:45,777 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 10:36:45,778 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 10:36:45,781 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 10:36:45,786 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 10:36:45,787 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 10:36:45,791 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 10:36:45,792 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 10:36:45,793 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 10:36:45,793 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 10:36:45,795 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 10:36:45,796 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 10:36:45,797 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 10:36:45,797 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 10:36:45,798 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 10:36:45,802 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 10:36:45,806 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 10:36:45,808 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 10:36:45,809 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 10:36:45,810 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 10:36:45,811 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 10:36:45,812 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 10:36:45,819 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 10:36:45,819 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 10:36:45,819 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 10:36:45,820 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 10:36:45,820 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 10:36:45,821 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 10:36:45,822 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 10:36:45,823 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 10:36:45,824 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 10:36:45,824 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 10:36:45,825 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 10:36:45,825 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 10:36:45,826 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 10:36:45,826 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 10:36:45,826 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 10:36:45,827 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 10:36:45,828 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 10:36:45,829 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-03-20 10:36:45,855 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 10:36:45,855 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 10:36:45,856 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-20 10:36:45,856 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-20 10:36:45,857 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-20 10:36:45,857 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-20 10:36:45,857 INFO L138 SettingsManager]: * Use SBE=true [2022-03-20 10:36:45,857 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 10:36:45,858 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 10:36:45,858 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 10:36:45,858 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 10:36:45,859 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 10:36:45,859 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 10:36:45,859 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 10:36:45,859 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 10:36:45,859 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 10:36:45,859 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 10:36:45,859 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 10:36:45,860 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 10:36:45,860 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 10:36:45,860 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 10:36:45,860 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-03-20 10:36:45,860 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-20 10:36:45,861 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-20 10:36:45,861 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-20 10:36:45,861 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-20 10:36:45,861 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-03-20 10:36:45,861 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-03-20 10:36:45,862 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-20 10:36:45,862 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-20 10:36:46,093 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 10:36:46,118 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 10:36:46,121 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 10:36:46,121 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 10:36:46,122 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 10:36:46,124 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c [2022-03-20 10:36:46,173 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/49308998e/781604e8ab1d4b6996cb8c5dd887e1b9/FLAGa34e944d2 [2022-03-20 10:36:46,565 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 10:36:46,566 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c [2022-03-20 10:36:46,572 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/49308998e/781604e8ab1d4b6996cb8c5dd887e1b9/FLAGa34e944d2 [2022-03-20 10:36:46,976 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/49308998e/781604e8ab1d4b6996cb8c5dd887e1b9 [2022-03-20 10:36:46,978 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 10:36:46,979 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-20 10:36:46,981 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 10:36:46,981 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 10:36:46,985 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 10:36:46,986 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 10:36:46" (1/1) ... [2022-03-20 10:36:46,987 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@214401ac and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:36:46, skipping insertion in model container [2022-03-20 10:36:46,987 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 10:36:46" (1/1) ... [2022-03-20 10:36:46,992 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 10:36:47,006 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 10:36:47,141 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c[538,551] [2022-03-20 10:36:47,166 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 10:36:47,177 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 10:36:47,189 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c[538,551] [2022-03-20 10:36:47,206 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 10:36:47,218 INFO L208 MainTranslator]: Completed translation [2022-03-20 10:36:47,218 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:36:47 WrapperNode [2022-03-20 10:36:47,219 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 10:36:47,222 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 10:36:47,222 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 10:36:47,222 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 10:36:47,232 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:36:47" (1/1) ... [2022-03-20 10:36:47,232 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:36:47" (1/1) ... [2022-03-20 10:36:47,238 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:36:47" (1/1) ... [2022-03-20 10:36:47,238 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:36:47" (1/1) ... [2022-03-20 10:36:47,248 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:36:47" (1/1) ... [2022-03-20 10:36:47,253 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:36:47" (1/1) ... [2022-03-20 10:36:47,260 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:36:47" (1/1) ... [2022-03-20 10:36:47,262 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 10:36:47,263 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 10:36:47,263 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 10:36:47,263 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 10:36:47,264 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:36:47" (1/1) ... [2022-03-20 10:36:47,270 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 10:36:47,278 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:36:47,292 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-20 10:36:47,307 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-20 10:36:47,337 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 10:36:47,337 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 10:36:47,337 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 10:36:47,338 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 10:36:47,338 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 10:36:47,338 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 10:36:47,338 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 10:36:47,339 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 10:36:47,339 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 10:36:47,340 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 10:36:47,340 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-03-20 10:36:47,340 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 10:36:47,340 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 10:36:47,340 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 10:36:47,340 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 10:36:47,340 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 10:36:47,340 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 10:36:47,340 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 10:36:47,341 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 10:36:47,341 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 10:36:47,397 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 10:36:47,399 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 10:36:47,543 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 10:36:47,548 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 10:36:47,548 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-20 10:36:47,550 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 10:36:47 BoogieIcfgContainer [2022-03-20 10:36:47,550 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 10:36:47,550 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-20 10:36:47,550 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-20 10:36:47,564 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-20 10:36:47,567 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 10:36:47" (1/1) ... [2022-03-20 10:36:47,568 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_QVASR [2022-03-20 10:36:47,581 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 20.03 10:36:47 BasicIcfg [2022-03-20 10:36:47,582 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-20 10:36:47,603 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 10:36:47,603 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 10:36:47,607 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 10:36:47,607 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 10:36:46" (1/4) ... [2022-03-20 10:36:47,608 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7c5102b3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 10:36:47, skipping insertion in model container [2022-03-20 10:36:47,608 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:36:47" (2/4) ... [2022-03-20 10:36:47,608 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7c5102b3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 10:36:47, skipping insertion in model container [2022-03-20 10:36:47,608 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 10:36:47" (3/4) ... [2022-03-20 10:36:47,608 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7c5102b3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.03 10:36:47, skipping insertion in model container [2022-03-20 10:36:47,609 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 20.03 10:36:47" (4/4) ... [2022-03-20 10:36:47,609 INFO L111 eAbstractionObserver]: Analyzing ICFG hard-ll_valuebound20.cqvasr [2022-03-20 10:36:47,614 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-03-20 10:36:47,614 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 10:36:47,669 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 10:36:47,681 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-20 10:36:47,682 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 10:36:47,706 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 10:36:47,711 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-20 10:36:47,712 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:36:47,712 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:36:47,713 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:36:47,720 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:36:47,720 INFO L85 PathProgramCache]: Analyzing trace with hash 1011787902, now seen corresponding path program 1 times [2022-03-20 10:36:47,728 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:36:47,729 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1386870437] [2022-03-20 10:36:47,729 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:36:47,730 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:36:47,829 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:47,896 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 10:36:47,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:47,919 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 10:36:47,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:47,928 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-20 10:36:47,930 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:47,937 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-20 10:36:47,939 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:47,944 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 10:36:47,944 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:36:47,945 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1386870437] [2022-03-20 10:36:47,945 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1386870437] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 10:36:47,945 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 10:36:47,946 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 10:36:47,947 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2027894183] [2022-03-20 10:36:47,947 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:36:47,951 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-20 10:36:47,951 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:36:47,973 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-20 10:36:47,973 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 10:36:47,975 INFO L87 Difference]: Start difference. First operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 10:36:48,042 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:36:48,042 INFO L93 Difference]: Finished difference Result 69 states and 110 transitions. [2022-03-20 10:36:48,043 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-20 10:36:48,044 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-03-20 10:36:48,045 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:36:48,050 INFO L225 Difference]: With dead ends: 69 [2022-03-20 10:36:48,051 INFO L226 Difference]: Without dead ends: 33 [2022-03-20 10:36:48,053 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 12 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-20 10:36:48,056 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 21 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 41 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.0s IncrementalHoareTripleChecker+Time [2022-03-20 10:36:48,057 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 41 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 10:36:48,071 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-03-20 10:36:48,087 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-03-20 10:36:48,088 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 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-20 10:36:48,089 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2022-03-20 10:36:48,090 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 28 [2022-03-20 10:36:48,091 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:36:48,091 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2022-03-20 10:36:48,091 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 10:36:48,091 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-03-20 10:36:48,092 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-20 10:36:48,093 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:36:48,093 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:36:48,093 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 10:36:48,093 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:36:48,094 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:36:48,094 INFO L85 PathProgramCache]: Analyzing trace with hash -1710049411, now seen corresponding path program 1 times [2022-03-20 10:36:48,094 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:36:48,094 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1469017609] [2022-03-20 10:36:48,095 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:36:48,095 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:36:48,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:48,186 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 10:36:48,188 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:48,193 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 10:36:48,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:48,201 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-20 10:36:48,202 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:48,217 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-20 10:36:48,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:48,222 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 10:36:48,222 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:36:48,222 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1469017609] [2022-03-20 10:36:48,222 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1469017609] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 10:36:48,222 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 10:36:48,223 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 10:36:48,223 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1732598396] [2022-03-20 10:36:48,223 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:36:48,224 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 10:36:48,224 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:36:48,224 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 10:36:48,225 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 10:36:48,227 INFO L87 Difference]: Start difference. First operand 33 states and 43 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-03-20 10:36:48,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:36:48,473 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-03-20 10:36:48,474 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 10:36:48,474 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2022-03-20 10:36:48,474 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:36:48,476 INFO L225 Difference]: With dead ends: 46 [2022-03-20 10:36:48,476 INFO L226 Difference]: Without dead ends: 44 [2022-03-20 10:36:48,480 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-20 10:36:48,481 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 38 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 155 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 10:36:48,482 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 48 Invalid, 155 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 10:36:48,484 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-03-20 10:36:48,499 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-03-20 10:36:48,500 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 20 states have (on average 1.2) internal successors, (24), 21 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-20 10:36:48,503 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 46 transitions. [2022-03-20 10:36:48,503 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 46 transitions. Word has length 28 [2022-03-20 10:36:48,503 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:36:48,503 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 46 transitions. [2022-03-20 10:36:48,504 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-03-20 10:36:48,504 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 46 transitions. [2022-03-20 10:36:48,505 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-03-20 10:36:48,505 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:36:48,505 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 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-20 10:36:48,506 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-20 10:36:48,506 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:36:48,507 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:36:48,507 INFO L85 PathProgramCache]: Analyzing trace with hash 1042498848, now seen corresponding path program 1 times [2022-03-20 10:36:48,507 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:36:48,507 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2066957847] [2022-03-20 10:36:48,507 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:36:48,508 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:36:48,531 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:48,609 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 10:36:48,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:48,633 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 10:36:48,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:48,639 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-20 10:36:48,640 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:48,646 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-20 10:36:48,647 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:48,655 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2022-03-20 10:36:48,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:48,669 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 10:36:48,669 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:36:48,669 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2066957847] [2022-03-20 10:36:48,670 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2066957847] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 10:36:48,670 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 10:36:48,670 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 10:36:48,670 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [512471441] [2022-03-20 10:36:48,670 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:36:48,670 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 10:36:48,671 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:36:48,671 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 10:36:48,671 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 10:36:48,671 INFO L87 Difference]: Start difference. First operand 37 states and 46 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 10:36:48,828 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:36:48,829 INFO L93 Difference]: Finished difference Result 50 states and 63 transitions. [2022-03-20 10:36:48,829 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 10:36:48,830 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-03-20 10:36:48,830 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:36:48,831 INFO L225 Difference]: With dead ends: 50 [2022-03-20 10:36:48,831 INFO L226 Difference]: Without dead ends: 48 [2022-03-20 10:36:48,833 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-20 10:36:48,838 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 33 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 10:36:48,839 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 48 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 132 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 10:36:48,840 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-03-20 10:36:48,847 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 41. [2022-03-20 10:36:48,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-20 10:36:48,848 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2022-03-20 10:36:48,848 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 33 [2022-03-20 10:36:48,849 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:36:48,849 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2022-03-20 10:36:48,849 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 10:36:48,849 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2022-03-20 10:36:48,850 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-03-20 10:36:48,850 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:36:48,850 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:36:48,850 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-03-20 10:36:48,850 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:36:48,851 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:36:48,851 INFO L85 PathProgramCache]: Analyzing trace with hash 1436069466, now seen corresponding path program 1 times [2022-03-20 10:36:48,851 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:36:48,851 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2043410276] [2022-03-20 10:36:48,851 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:36:48,851 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:36:48,862 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:36:48,862 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [667286428] [2022-03-20 10:36:48,862 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:36:48,862 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:36:48,863 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:36:48,864 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-20 10:36:48,865 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-20 10:36:48,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:48,916 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-20 10:36:48,921 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:36:49,116 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2022-03-20 10:36:49,116 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 10:36:49,116 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:36:49,116 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2043410276] [2022-03-20 10:36:49,116 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:36:49,117 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [667286428] [2022-03-20 10:36:49,117 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [667286428] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 10:36:49,117 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 10:36:49,117 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-03-20 10:36:49,117 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1787896593] [2022-03-20 10:36:49,117 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:36:49,118 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-20 10:36:49,118 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:36:49,118 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-20 10:36:49,119 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2022-03-20 10:36:49,119 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-20 10:36:49,222 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:36:49,222 INFO L93 Difference]: Finished difference Result 69 states and 89 transitions. [2022-03-20 10:36:49,223 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-20 10:36:49,223 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) Word has length 38 [2022-03-20 10:36:49,223 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:36:49,224 INFO L225 Difference]: With dead ends: 69 [2022-03-20 10:36:49,224 INFO L226 Difference]: Without dead ends: 55 [2022-03-20 10:36:49,225 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2022-03-20 10:36:49,225 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 20 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 225 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 10:36:49,226 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 225 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 99 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 10:36:49,226 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-03-20 10:36:49,234 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-03-20 10:36:49,235 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 30 states have (on average 1.1666666666666667) internal successors, (35), 32 states have internal predecessors, (35), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-03-20 10:36:49,236 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-03-20 10:36:49,236 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 38 [2022-03-20 10:36:49,236 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:36:49,236 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-03-20 10:36:49,236 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-20 10:36:49,236 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-03-20 10:36:49,237 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-03-20 10:36:49,237 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:36:49,237 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:36:49,260 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-03-20 10:36:49,459 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:36:49,460 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:36:49,460 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:36:49,460 INFO L85 PathProgramCache]: Analyzing trace with hash 5711864, now seen corresponding path program 1 times [2022-03-20 10:36:49,460 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:36:49,460 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1345918116] [2022-03-20 10:36:49,460 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:36:49,461 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:36:49,471 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:36:49,471 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [237145452] [2022-03-20 10:36:49,471 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:36:49,471 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:36:49,471 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:36:49,474 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-20 10:36:49,475 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-20 10:36:49,515 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:49,516 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-20 10:36:49,518 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:36:49,818 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 9 proven. 3 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-03-20 10:36:49,818 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:36:50,004 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-20 10:36:50,004 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:36:50,005 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1345918116] [2022-03-20 10:36:50,005 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:36:50,005 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [237145452] [2022-03-20 10:36:50,005 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [237145452] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 10:36:50,005 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 10:36:50,005 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [9] total 11 [2022-03-20 10:36:50,006 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1521575919] [2022-03-20 10:36:50,006 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:36:50,006 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 10:36:50,006 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:36:50,007 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 10:36:50,007 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-03-20 10:36:50,007 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 10:36:50,080 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:36:50,080 INFO L93 Difference]: Finished difference Result 68 states and 85 transitions. [2022-03-20 10:36:50,080 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 10:36:50,080 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 45 [2022-03-20 10:36:50,081 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:36:50,081 INFO L225 Difference]: With dead ends: 68 [2022-03-20 10:36:50,082 INFO L226 Difference]: Without dead ends: 66 [2022-03-20 10:36:50,082 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-03-20 10:36:50,083 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 16 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 10:36:50,083 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 145 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 10:36:50,084 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-03-20 10:36:50,093 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 64. [2022-03-20 10:36:50,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 36 states have (on average 1.1944444444444444) internal successors, (43), 38 states have internal predecessors, (43), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-03-20 10:36:50,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 80 transitions. [2022-03-20 10:36:50,095 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 80 transitions. Word has length 45 [2022-03-20 10:36:50,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:36:50,095 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 80 transitions. [2022-03-20 10:36:50,096 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 10:36:50,096 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 80 transitions. [2022-03-20 10:36:50,097 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-03-20 10:36:50,097 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:36:50,097 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:36:50,123 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-20 10:36:50,311 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:36:50,312 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:36:50,312 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:36:50,312 INFO L85 PathProgramCache]: Analyzing trace with hash 1597443315, now seen corresponding path program 1 times [2022-03-20 10:36:50,312 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:36:50,313 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [800343307] [2022-03-20 10:36:50,313 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:36:50,313 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:36:50,323 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:36:50,323 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [94581084] [2022-03-20 10:36:50,323 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:36:50,323 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:36:50,323 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:36:50,330 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-20 10:36:50,366 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-20 10:36:50,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:50,394 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 16 conjunts are in the unsatisfiable core [2022-03-20 10:36:50,397 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:36:50,637 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 16 proven. 4 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2022-03-20 10:36:50,637 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:36:50,790 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2022-03-20 10:36:50,791 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:36:50,791 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [800343307] [2022-03-20 10:36:50,791 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:36:50,791 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [94581084] [2022-03-20 10:36:50,793 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [94581084] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 10:36:50,793 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 10:36:50,793 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-03-20 10:36:50,794 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [43721271] [2022-03-20 10:36:50,794 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:36:50,795 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 10:36:50,795 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:36:50,796 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 10:36:50,796 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-03-20 10:36:50,797 INFO L87 Difference]: Start difference. First operand 64 states and 80 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, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 10:36:50,900 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:36:50,901 INFO L93 Difference]: Finished difference Result 76 states and 95 transitions. [2022-03-20 10:36:50,901 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 10:36:50,901 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, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 55 [2022-03-20 10:36:50,902 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:36:50,903 INFO L225 Difference]: With dead ends: 76 [2022-03-20 10:36:50,903 INFO L226 Difference]: Without dead ends: 74 [2022-03-20 10:36:50,903 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 99 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-03-20 10:36:50,904 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 8 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 10:36:50,904 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 141 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 10:36:50,905 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2022-03-20 10:36:50,915 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2022-03-20 10:36:50,915 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 40 states have (on average 1.175) internal successors, (47), 43 states have internal predecessors, (47), 22 states have call successors, (22), 9 states have call predecessors, (22), 8 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-03-20 10:36:50,916 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 88 transitions. [2022-03-20 10:36:50,916 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 88 transitions. Word has length 55 [2022-03-20 10:36:50,917 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:36:50,917 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 88 transitions. [2022-03-20 10:36:50,917 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, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 10:36:50,917 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 88 transitions. [2022-03-20 10:36:50,918 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-03-20 10:36:50,919 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:36:50,919 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:36:50,937 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2022-03-20 10:36:51,123 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:36:51,124 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:36:51,124 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:36:51,124 INFO L85 PathProgramCache]: Analyzing trace with hash 810354846, now seen corresponding path program 1 times [2022-03-20 10:36:51,125 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:36:51,125 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1358259046] [2022-03-20 10:36:51,125 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:36:51,125 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:36:51,136 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:36:51,137 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2079325015] [2022-03-20 10:36:51,137 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:36:51,137 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:36:51,137 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:36:51,146 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-20 10:36:51,148 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-20 10:36:51,189 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:51,191 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 10:36:51,197 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:36:51,343 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-03-20 10:36:51,343 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 10:36:51,343 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:36:51,343 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1358259046] [2022-03-20 10:36:51,343 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:36:51,344 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2079325015] [2022-03-20 10:36:51,344 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2079325015] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 10:36:51,344 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 10:36:51,346 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 10:36:51,347 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2067180130] [2022-03-20 10:36:51,347 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:36:51,348 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 10:36:51,349 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:36:51,349 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 10:36:51,349 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 10:36:51,349 INFO L87 Difference]: Start difference. First operand 71 states and 88 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-03-20 10:36:51,410 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:36:51,410 INFO L93 Difference]: Finished difference Result 79 states and 96 transitions. [2022-03-20 10:36:51,411 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 10:36:51,411 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 56 [2022-03-20 10:36:51,414 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:36:51,415 INFO L225 Difference]: With dead ends: 79 [2022-03-20 10:36:51,415 INFO L226 Difference]: Without dead ends: 72 [2022-03-20 10:36:51,416 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 52 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-20 10:36:51,416 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 8 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 10:36:51,417 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 132 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 10:36:51,417 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2022-03-20 10:36:51,426 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 71. [2022-03-20 10:36:51,426 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 41 states have (on average 1.146341463414634) internal successors, (47), 44 states have internal predecessors, (47), 20 states have call successors, (20), 10 states have call predecessors, (20), 9 states have return successors, (18), 16 states have call predecessors, (18), 18 states have call successors, (18) [2022-03-20 10:36:51,427 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 85 transitions. [2022-03-20 10:36:51,427 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 85 transitions. Word has length 56 [2022-03-20 10:36:51,427 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:36:51,428 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 85 transitions. [2022-03-20 10:36:51,428 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-03-20 10:36:51,428 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 85 transitions. [2022-03-20 10:36:51,430 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-03-20 10:36:51,430 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:36:51,430 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:36:51,448 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-20 10:36:51,639 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:36:51,640 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:36:51,640 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:36:51,640 INFO L85 PathProgramCache]: Analyzing trace with hash 1689231171, now seen corresponding path program 1 times [2022-03-20 10:36:51,640 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:36:51,640 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2016650887] [2022-03-20 10:36:51,640 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:36:51,640 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:36:51,649 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:36:51,649 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [90272803] [2022-03-20 10:36:51,649 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:36:51,649 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:36:51,650 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:36:51,651 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-20 10:36:51,655 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-20 10:36:51,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:36:51,727 INFO L263 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 30 conjunts are in the unsatisfiable core [2022-03-20 10:36:51,729 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:36:52,514 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 36 proven. 8 refuted. 0 times theorem prover too weak. 103 trivial. 0 not checked. [2022-03-20 10:36:52,514 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:37:34,623 WARN L232 SmtUtils]: Spent 29.24s on a formula simplification that was a NOOP. DAG size: 53 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 10:38:50,530 WARN L232 SmtUtils]: Spent 22.62s on a formula simplification that was a NOOP. DAG size: 54 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 10:39:56,644 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 36 proven. 8 refuted. 0 times theorem prover too weak. 103 trivial. 0 not checked. [2022-03-20 10:39:56,644 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:39:56,644 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2016650887] [2022-03-20 10:39:56,644 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:39:56,645 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [90272803] [2022-03-20 10:39:56,645 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [90272803] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:39:56,645 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:39:56,645 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12] total 18 [2022-03-20 10:39:56,645 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1757599540] [2022-03-20 10:39:56,645 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:39:56,645 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-03-20 10:39:56,646 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:39:56,646 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-03-20 10:39:56,646 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=241, Unknown=0, NotChecked=0, Total=306 [2022-03-20 10:39:56,646 INFO L87 Difference]: Start difference. First operand 71 states and 85 transitions. Second operand has 18 states, 18 states have (on average 2.0) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) [2022-03-20 10:39:58,658 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-20 10:40:13,523 WARN L232 SmtUtils]: Spent 13.65s on a formula simplification. DAG size of input: 57 DAG size of output: 27 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 10:40:31,018 WARN L232 SmtUtils]: Spent 15.74s on a formula simplification that was a NOOP. DAG size: 70 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 10:40:32,678 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.59s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 10:40:41,086 WARN L232 SmtUtils]: Spent 7.06s on a formula simplification. DAG size of input: 58 DAG size of output: 27 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 10:40:48,152 WARN L232 SmtUtils]: Spent 6.08s on a formula simplification. DAG size of input: 63 DAG size of output: 29 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 10:40:49,358 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:40:49,358 INFO L93 Difference]: Finished difference Result 148 states and 194 transitions. [2022-03-20 10:40:49,359 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2022-03-20 10:40:49,359 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 2.0) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) Word has length 75 [2022-03-20 10:40:49,359 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:40:49,360 INFO L225 Difference]: With dead ends: 148 [2022-03-20 10:40:49,361 INFO L226 Difference]: Without dead ends: 121 [2022-03-20 10:40:49,361 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 131 SyntacticMatches, 2 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 111 ImplicationChecksByTransitivity, 97.0s TimeCoverageRelationStatistics Valid=136, Invalid=514, Unknown=0, NotChecked=0, Total=650 [2022-03-20 10:40:49,362 INFO L913 BasicCegarLoop]: 37 mSDtfsCounter, 64 mSDsluCounter, 240 mSDsCounter, 0 mSdLazyCounter, 398 mSolverCounterSat, 142 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 277 SdHoareTripleChecker+Invalid, 541 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 142 IncrementalHoareTripleChecker+Valid, 398 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.0s IncrementalHoareTripleChecker+Time [2022-03-20 10:40:49,362 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [69 Valid, 277 Invalid, 541 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [142 Valid, 398 Invalid, 1 Unknown, 0 Unchecked, 9.0s Time] [2022-03-20 10:40:49,364 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2022-03-20 10:40:49,382 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 103. [2022-03-20 10:40:49,383 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 60 states have (on average 1.15) internal successors, (69), 65 states have internal predecessors, (69), 30 states have call successors, (30), 13 states have call predecessors, (30), 12 states have return successors, (28), 24 states have call predecessors, (28), 28 states have call successors, (28) [2022-03-20 10:40:49,387 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 127 transitions. [2022-03-20 10:40:49,387 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 127 transitions. Word has length 75 [2022-03-20 10:40:49,387 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:40:49,388 INFO L478 AbstractCegarLoop]: Abstraction has 103 states and 127 transitions. [2022-03-20 10:40:49,388 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 2.0) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) [2022-03-20 10:40:49,388 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 127 transitions. [2022-03-20 10:40:49,390 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2022-03-20 10:40:49,390 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:40:49,390 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:40:49,407 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-20 10:40:49,590 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:40:49,591 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:40:49,591 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:40:49,591 INFO L85 PathProgramCache]: Analyzing trace with hash -102783885, now seen corresponding path program 1 times [2022-03-20 10:40:49,591 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:40:49,591 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1621543966] [2022-03-20 10:40:49,591 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:40:49,591 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:40:49,601 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:40:49,601 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [546875856] [2022-03-20 10:40:49,601 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:40:49,602 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:40:49,602 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:40:49,614 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-20 10:40:49,615 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-20 10:40:49,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:40:49,661 INFO L263 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-20 10:40:49,663 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:40:49,872 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 20 proven. 4 refuted. 0 times theorem prover too weak. 197 trivial. 0 not checked. [2022-03-20 10:40:49,872 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:40:50,131 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 20 proven. 4 refuted. 0 times theorem prover too weak. 197 trivial. 0 not checked. [2022-03-20 10:40:50,132 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:40:50,132 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1621543966] [2022-03-20 10:40:50,132 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:40:50,132 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [546875856] [2022-03-20 10:40:50,132 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [546875856] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:40:50,132 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:40:50,132 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2022-03-20 10:40:50,132 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1513720144] [2022-03-20 10:40:50,133 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:40:50,133 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 10:40:50,133 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:40:50,133 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 10:40:50,134 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2022-03-20 10:40:50,134 INFO L87 Difference]: Start difference. First operand 103 states and 127 transitions. Second operand has 9 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2022-03-20 10:40:50,339 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:40:50,339 INFO L93 Difference]: Finished difference Result 116 states and 143 transitions. [2022-03-20 10:40:50,339 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 10:40:50,339 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) Word has length 86 [2022-03-20 10:40:50,340 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:40:50,341 INFO L225 Difference]: With dead ends: 116 [2022-03-20 10:40:50,341 INFO L226 Difference]: Without dead ends: 114 [2022-03-20 10:40:50,341 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 162 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2022-03-20 10:40:50,342 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 15 mSDsluCounter, 182 mSDsCounter, 0 mSdLazyCounter, 94 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 226 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 94 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 10:40:50,342 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 226 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 94 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 10:40:50,343 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2022-03-20 10:40:50,355 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 107. [2022-03-20 10:40:50,355 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 62 states have (on average 1.1612903225806452) internal successors, (72), 67 states have internal predecessors, (72), 32 states have call successors, (32), 13 states have call predecessors, (32), 12 states have return successors, (30), 26 states have call predecessors, (30), 30 states have call successors, (30) [2022-03-20 10:40:50,356 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 134 transitions. [2022-03-20 10:40:50,357 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 134 transitions. Word has length 86 [2022-03-20 10:40:50,357 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:40:50,357 INFO L478 AbstractCegarLoop]: Abstraction has 107 states and 134 transitions. [2022-03-20 10:40:50,357 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2022-03-20 10:40:50,357 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 134 transitions. [2022-03-20 10:40:50,359 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2022-03-20 10:40:50,359 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:40:50,359 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:40:50,383 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-20 10:40:50,581 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:40:50,582 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:40:50,582 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:40:50,582 INFO L85 PathProgramCache]: Analyzing trace with hash 1406960063, now seen corresponding path program 2 times [2022-03-20 10:40:50,583 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:40:50,583 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1850746775] [2022-03-20 10:40:50,583 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:40:50,583 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:40:50,601 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:40:50,602 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [177434478] [2022-03-20 10:40:50,602 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 10:40:50,602 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:40:50,602 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:40:50,608 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-20 10:40:50,610 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-20 10:40:50,664 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 10:40:50,664 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 10:40:50,664 INFO L263 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 10:40:50,666 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:40:50,805 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2022-03-20 10:40:50,805 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:40:50,970 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2022-03-20 10:40:50,970 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:40:50,970 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1850746775] [2022-03-20 10:40:50,970 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:40:50,970 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [177434478] [2022-03-20 10:40:50,971 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [177434478] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:40:50,971 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:40:50,971 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2022-03-20 10:40:50,971 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1199985616] [2022-03-20 10:40:50,971 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:40:50,971 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 10:40:50,972 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:40:50,972 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 10:40:50,972 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-20 10:40:50,972 INFO L87 Difference]: Start difference. First operand 107 states and 134 transitions. Second operand has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 5 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 4 states have call predecessors, (19), 4 states have call successors, (19) [2022-03-20 10:40:51,080 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:40:51,080 INFO L93 Difference]: Finished difference Result 130 states and 164 transitions. [2022-03-20 10:40:51,081 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-03-20 10:40:51,081 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 5 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 4 states have call predecessors, (19), 4 states have call successors, (19) Word has length 88 [2022-03-20 10:40:51,081 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:40:51,083 INFO L225 Difference]: With dead ends: 130 [2022-03-20 10:40:51,083 INFO L226 Difference]: Without dead ends: 111 [2022-03-20 10:40:51,083 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 171 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-20 10:40:51,084 INFO L913 BasicCegarLoop]: 56 mSDtfsCounter, 1 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 181 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 10:40:51,084 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 181 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 10:40:51,085 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2022-03-20 10:40:51,098 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 111. [2022-03-20 10:40:51,099 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 64 states have (on average 1.15625) internal successors, (74), 69 states have internal predecessors, (74), 34 states have call successors, (34), 13 states have call predecessors, (34), 12 states have return successors, (32), 28 states have call predecessors, (32), 32 states have call successors, (32) [2022-03-20 10:40:51,100 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 140 transitions. [2022-03-20 10:40:51,100 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 140 transitions. Word has length 88 [2022-03-20 10:40:51,100 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:40:51,100 INFO L478 AbstractCegarLoop]: Abstraction has 111 states and 140 transitions. [2022-03-20 10:40:51,100 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 5 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 4 states have call predecessors, (19), 4 states have call successors, (19) [2022-03-20 10:40:51,100 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 140 transitions. [2022-03-20 10:40:51,101 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-03-20 10:40:51,101 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:40:51,102 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:40:51,129 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-20 10:40:51,329 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:40:51,330 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:40:51,330 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:40:51,330 INFO L85 PathProgramCache]: Analyzing trace with hash 966352941, now seen corresponding path program 1 times [2022-03-20 10:40:51,331 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:40:51,331 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1812921009] [2022-03-20 10:40:51,331 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:40:51,331 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:40:51,352 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:40:51,352 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [235256367] [2022-03-20 10:40:51,353 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:40:51,353 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:40:51,353 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:40:51,354 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-20 10:40:51,356 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-20 10:40:51,407 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:40:51,409 INFO L263 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-20 10:40:51,411 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:40:51,688 INFO L134 CoverageAnalysis]: Checked inductivity of 263 backedges. 22 proven. 9 refuted. 0 times theorem prover too weak. 232 trivial. 0 not checked. [2022-03-20 10:40:51,688 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:40:52,078 INFO L134 CoverageAnalysis]: Checked inductivity of 263 backedges. 22 proven. 9 refuted. 0 times theorem prover too weak. 232 trivial. 0 not checked. [2022-03-20 10:40:52,078 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:40:52,078 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1812921009] [2022-03-20 10:40:52,078 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:40:52,078 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [235256367] [2022-03-20 10:40:52,078 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [235256367] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:40:52,078 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:40:52,079 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2022-03-20 10:40:52,079 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1644179252] [2022-03-20 10:40:52,079 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:40:52,079 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-20 10:40:52,079 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:40:52,080 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-20 10:40:52,080 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-03-20 10:40:52,080 INFO L87 Difference]: Start difference. First operand 111 states and 140 transitions. Second operand has 11 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 8 states have call successors, (29), 2 states have call predecessors, (29), 1 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2022-03-20 10:40:52,357 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:40:52,357 INFO L93 Difference]: Finished difference Result 119 states and 148 transitions. [2022-03-20 10:40:52,358 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 10:40:52,358 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 8 states have call successors, (29), 2 states have call predecessors, (29), 1 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 91 [2022-03-20 10:40:52,358 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:40:52,359 INFO L225 Difference]: With dead ends: 119 [2022-03-20 10:40:52,359 INFO L226 Difference]: Without dead ends: 102 [2022-03-20 10:40:52,361 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 171 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=139, Unknown=0, NotChecked=0, Total=182 [2022-03-20 10:40:52,361 INFO L913 BasicCegarLoop]: 58 mSDtfsCounter, 10 mSDsluCounter, 308 mSDsCounter, 0 mSdLazyCounter, 119 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 366 SdHoareTripleChecker+Invalid, 131 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 119 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 10:40:52,361 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 366 Invalid, 131 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 119 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 10:40:52,362 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2022-03-20 10:40:52,379 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 102. [2022-03-20 10:40:52,380 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 59 states have (on average 1.152542372881356) internal successors, (68), 64 states have internal predecessors, (68), 30 states have call successors, (30), 13 states have call predecessors, (30), 12 states have return successors, (28), 24 states have call predecessors, (28), 28 states have call successors, (28) [2022-03-20 10:40:52,381 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 126 transitions. [2022-03-20 10:40:52,381 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 126 transitions. Word has length 91 [2022-03-20 10:40:52,381 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:40:52,382 INFO L478 AbstractCegarLoop]: Abstraction has 102 states and 126 transitions. [2022-03-20 10:40:52,382 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 8 states have call successors, (29), 2 states have call predecessors, (29), 1 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2022-03-20 10:40:52,382 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 126 transitions. [2022-03-20 10:40:52,383 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2022-03-20 10:40:52,383 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:40:52,383 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2022-03-20 10:40:52,409 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-20 10:40:52,599 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,SelfDestructingSolverStorable10 [2022-03-20 10:40:52,600 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:40:52,600 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:40:52,600 INFO L85 PathProgramCache]: Analyzing trace with hash -1871497790, now seen corresponding path program 1 times [2022-03-20 10:40:52,600 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:40:52,600 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1822963933] [2022-03-20 10:40:52,600 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:40:52,601 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:40:52,608 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:40:52,608 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2022897625] [2022-03-20 10:40:52,608 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:40:52,608 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:40:52,608 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:40:52,609 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-20 10:40:52,636 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-20 10:40:52,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:40:52,661 INFO L263 TraceCheckSpWp]: Trace formula consists of 212 conjuncts, 4 conjunts are in the unsatisfiable core [2022-03-20 10:40:52,663 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:40:52,851 INFO L134 CoverageAnalysis]: Checked inductivity of 315 backedges. 81 proven. 0 refuted. 0 times theorem prover too weak. 234 trivial. 0 not checked. [2022-03-20 10:40:52,851 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 10:40:52,851 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:40:52,851 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1822963933] [2022-03-20 10:40:52,851 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:40:52,852 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2022897625] [2022-03-20 10:40:52,852 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2022897625] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 10:40:52,852 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 10:40:52,852 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 10:40:52,852 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [142270220] [2022-03-20 10:40:52,852 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:40:52,852 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 10:40:52,852 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:40:52,853 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 10:40:52,853 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-03-20 10:40:52,853 INFO L87 Difference]: Start difference. First operand 102 states and 126 transitions. Second operand has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-03-20 10:40:52,926 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:40:52,926 INFO L93 Difference]: Finished difference Result 116 states and 141 transitions. [2022-03-20 10:40:52,926 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 10:40:52,927 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 95 [2022-03-20 10:40:52,927 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:40:52,927 INFO L225 Difference]: With dead ends: 116 [2022-03-20 10:40:52,928 INFO L226 Difference]: Without dead ends: 104 [2022-03-20 10:40:52,928 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-03-20 10:40:52,928 INFO L913 BasicCegarLoop]: 57 mSDtfsCounter, 9 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 10:40:52,929 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 163 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 10:40:52,929 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2022-03-20 10:40:52,939 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 104. [2022-03-20 10:40:52,940 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 61 states have (on average 1.1311475409836065) internal successors, (69), 64 states have internal predecessors, (69), 30 states have call successors, (30), 13 states have call predecessors, (30), 12 states have return successors, (28), 26 states have call predecessors, (28), 28 states have call successors, (28) [2022-03-20 10:40:52,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 127 transitions. [2022-03-20 10:40:52,940 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 127 transitions. Word has length 95 [2022-03-20 10:40:52,941 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:40:52,941 INFO L478 AbstractCegarLoop]: Abstraction has 104 states and 127 transitions. [2022-03-20 10:40:52,941 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-03-20 10:40:52,941 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 127 transitions. [2022-03-20 10:40:52,942 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2022-03-20 10:40:52,942 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:40:52,942 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:40:52,966 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-20 10:40:53,163 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:40:53,163 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:40:53,164 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:40:53,164 INFO L85 PathProgramCache]: Analyzing trace with hash -317970408, now seen corresponding path program 3 times [2022-03-20 10:40:53,164 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:40:53,164 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [294730574] [2022-03-20 10:40:53,164 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:40:53,164 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:40:53,176 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:40:53,176 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1639561989] [2022-03-20 10:40:53,176 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-20 10:40:53,176 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:40:53,176 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:40:53,181 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-20 10:40:53,184 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-20 10:40:53,249 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-20 10:40:53,250 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 10:40:53,250 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 45 conjunts are in the unsatisfiable core [2022-03-20 10:40:53,253 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:40:53,990 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 37 proven. 55 refuted. 0 times theorem prover too weak. 282 trivial. 0 not checked. [2022-03-20 10:40:53,990 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:41:44,419 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 31 proven. 51 refuted. 4 times theorem prover too weak. 288 trivial. 0 not checked. [2022-03-20 10:41:44,419 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:41:44,419 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [294730574] [2022-03-20 10:41:44,419 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:41:44,419 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1639561989] [2022-03-20 10:41:44,419 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1639561989] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:41:44,420 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:41:44,420 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 23 [2022-03-20 10:41:44,420 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1095421013] [2022-03-20 10:41:44,420 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:41:44,420 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-03-20 10:41:44,420 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:41:44,421 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-03-20 10:41:44,421 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=418, Unknown=3, NotChecked=0, Total=506 [2022-03-20 10:41:44,421 INFO L87 Difference]: Start difference. First operand 104 states and 127 transitions. Second operand has 23 states, 23 states have (on average 2.130434782608696) internal successors, (49), 20 states have internal predecessors, (49), 11 states have call successors, (33), 2 states have call predecessors, (33), 3 states have return successors, (31), 11 states have call predecessors, (31), 9 states have call successors, (31) [2022-03-20 10:43:00,155 WARN L232 SmtUtils]: Spent 1.24m on a formula simplification. DAG size of input: 196 DAG size of output: 46 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 10:43:02,161 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-20 10:43:03,506 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.32s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 10:43:06,201 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-20 10:43:08,206 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 10:45:21,486 WARN L232 SmtUtils]: Spent 2.17m on a formula simplification. DAG size of input: 172 DAG size of output: 164 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 10:46:37,531 WARN L232 SmtUtils]: Spent 1.26m on a formula simplification. DAG size of input: 195 DAG size of output: 47 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 10:46:39,681 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-20 10:46:46,644 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-20 10:46:48,651 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-20 10:46:50,655 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-20 10:46:52,658 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-20 10:48:32,265 WARN L232 SmtUtils]: Spent 1.61m on a formula simplification. DAG size of input: 181 DAG size of output: 110 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 10:48:50,344 WARN L232 SmtUtils]: Spent 12.33s on a formula simplification. DAG size of input: 85 DAG size of output: 29 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 10:49:01,910 WARN L232 SmtUtils]: Spent 9.79s on a formula simplification. DAG size of input: 84 DAG size of output: 27 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 10:49:05,795 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-20 10:49:07,887 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-20 10:49:14,145 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-20 10:49:16,183 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.69s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 10:49:17,479 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.24s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 10:49:17,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:49:17,731 INFO L93 Difference]: Finished difference Result 237 states and 310 transitions. [2022-03-20 10:49:17,731 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2022-03-20 10:49:17,732 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.130434782608696) internal successors, (49), 20 states have internal predecessors, (49), 11 states have call successors, (33), 2 states have call predecessors, (33), 3 states have return successors, (31), 11 states have call predecessors, (31), 9 states have call successors, (31) Word has length 105 [2022-03-20 10:49:17,732 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:49:17,733 INFO L225 Difference]: With dead ends: 237 [2022-03-20 10:49:17,733 INFO L226 Difference]: Without dead ends: 184 [2022-03-20 10:49:17,736 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 227 GetRequests, 184 SyntacticMatches, 4 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 333 ImplicationChecksByTransitivity, 430.6s TimeCoverageRelationStatistics Valid=281, Invalid=1354, Unknown=5, NotChecked=0, Total=1640 [2022-03-20 10:49:17,737 INFO L913 BasicCegarLoop]: 50 mSDtfsCounter, 156 mSDsluCounter, 421 mSDsCounter, 0 mSdLazyCounter, 845 mSolverCounterSat, 356 mSolverCounterUnsat, 11 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 37.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 169 SdHoareTripleChecker+Valid, 471 SdHoareTripleChecker+Invalid, 1212 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 356 IncrementalHoareTripleChecker+Valid, 845 IncrementalHoareTripleChecker+Invalid, 11 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 38.0s IncrementalHoareTripleChecker+Time [2022-03-20 10:49:17,737 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [169 Valid, 471 Invalid, 1212 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [356 Valid, 845 Invalid, 11 Unknown, 0 Unchecked, 38.0s Time] [2022-03-20 10:49:17,737 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2022-03-20 10:49:17,759 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 161. [2022-03-20 10:49:17,760 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 161 states, 96 states have (on average 1.125) internal successors, (108), 103 states have internal predecessors, (108), 46 states have call successors, (46), 19 states have call predecessors, (46), 18 states have return successors, (44), 38 states have call predecessors, (44), 44 states have call successors, (44) [2022-03-20 10:49:17,761 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 161 states to 161 states and 198 transitions. [2022-03-20 10:49:17,761 INFO L78 Accepts]: Start accepts. Automaton has 161 states and 198 transitions. Word has length 105 [2022-03-20 10:49:17,761 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:49:17,761 INFO L478 AbstractCegarLoop]: Abstraction has 161 states and 198 transitions. [2022-03-20 10:49:17,762 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.130434782608696) internal successors, (49), 20 states have internal predecessors, (49), 11 states have call successors, (33), 2 states have call predecessors, (33), 3 states have return successors, (31), 11 states have call predecessors, (31), 9 states have call successors, (31) [2022-03-20 10:49:17,762 INFO L276 IsEmpty]: Start isEmpty. Operand 161 states and 198 transitions. [2022-03-20 10:49:17,763 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2022-03-20 10:49:17,763 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:49:17,763 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:49:17,790 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-20 10:49:17,963 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,SelfDestructingSolverStorable12 [2022-03-20 10:49:17,964 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:49:17,964 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:49:17,964 INFO L85 PathProgramCache]: Analyzing trace with hash -1498631042, now seen corresponding path program 2 times [2022-03-20 10:49:17,964 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:49:17,964 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [952416303] [2022-03-20 10:49:17,965 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:49:17,965 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:49:17,982 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:49:17,982 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [983949734] [2022-03-20 10:49:17,982 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 10:49:17,982 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:49:17,982 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:49:17,989 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-20 10:49:17,991 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-20 10:49:18,102 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 10:49:18,102 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 10:49:18,104 INFO L263 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 49 conjunts are in the unsatisfiable core [2022-03-20 10:49:18,107 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:49:19,145 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 10:49:20,138 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 106 proven. 30 refuted. 0 times theorem prover too weak. 354 trivial. 0 not checked. [2022-03-20 10:49:20,138 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:49:20,540 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 110 proven. 2 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2022-03-20 10:49:20,541 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:49:20,541 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [952416303] [2022-03-20 10:49:20,541 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:49:20,541 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [983949734] [2022-03-20 10:49:20,541 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [983949734] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:49:20,541 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:49:20,541 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 9] total 20 [2022-03-20 10:49:20,541 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [186601437] [2022-03-20 10:49:20,542 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:49:20,542 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-03-20 10:49:20,542 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:49:20,542 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-03-20 10:49:20,543 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=302, Unknown=0, NotChecked=0, Total=380 [2022-03-20 10:49:20,543 INFO L87 Difference]: Start difference. First operand 161 states and 198 transitions. Second operand has 20 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 10 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 8 states have call successors, (26) [2022-03-20 10:49:21,526 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:49:21,526 INFO L93 Difference]: Finished difference Result 228 states and 277 transitions. [2022-03-20 10:49:21,527 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-03-20 10:49:21,527 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 10 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 8 states have call successors, (26) Word has length 116 [2022-03-20 10:49:21,528 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:49:21,528 INFO L225 Difference]: With dead ends: 228 [2022-03-20 10:49:21,529 INFO L226 Difference]: Without dead ends: 159 [2022-03-20 10:49:21,529 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 233 GetRequests, 211 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=91, Invalid=371, Unknown=0, NotChecked=0, Total=462 [2022-03-20 10:49:21,530 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 39 mSDsluCounter, 209 mSDsCounter, 0 mSdLazyCounter, 476 mSolverCounterSat, 74 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 254 SdHoareTripleChecker+Invalid, 550 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 74 IncrementalHoareTripleChecker+Valid, 476 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2022-03-20 10:49:21,530 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [52 Valid, 254 Invalid, 550 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [74 Valid, 476 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2022-03-20 10:49:21,530 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 159 states. [2022-03-20 10:49:21,548 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 159 to 138. [2022-03-20 10:49:21,549 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 84 states have (on average 1.1071428571428572) internal successors, (93), 89 states have internal predecessors, (93), 35 states have call successors, (35), 19 states have call predecessors, (35), 18 states have return successors, (33), 29 states have call predecessors, (33), 33 states have call successors, (33) [2022-03-20 10:49:21,550 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 161 transitions. [2022-03-20 10:49:21,550 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 161 transitions. Word has length 116 [2022-03-20 10:49:21,550 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:49:21,550 INFO L478 AbstractCegarLoop]: Abstraction has 138 states and 161 transitions. [2022-03-20 10:49:21,550 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 10 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 8 states have call successors, (26) [2022-03-20 10:49:21,551 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 161 transitions. [2022-03-20 10:49:21,552 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2022-03-20 10:49:21,552 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:49:21,552 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:49:21,578 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-20 10:49:21,775 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,SelfDestructingSolverStorable13 [2022-03-20 10:49:21,776 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:49:21,776 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:49:21,776 INFO L85 PathProgramCache]: Analyzing trace with hash -715358301, now seen corresponding path program 4 times [2022-03-20 10:49:21,776 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:49:21,776 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [118781512] [2022-03-20 10:49:21,776 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:49:21,776 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:49:21,786 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:49:21,786 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1736655189] [2022-03-20 10:49:21,786 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 10:49:21,787 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:49:21,787 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:49:21,788 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-20 10:49:21,790 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-20 10:49:21,868 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 10:49:21,868 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 10:49:21,870 INFO L263 TraceCheckSpWp]: Trace formula consists of 303 conjuncts, 51 conjunts are in the unsatisfiable core [2022-03-20 10:49:21,872 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:49:23,055 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 36 proven. 51 refuted. 0 times theorem prover too weak. 624 trivial. 0 not checked. [2022-03-20 10:49:23,055 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:50:21,661 WARN L232 SmtUtils]: Spent 6.14s on a formula simplification that was a NOOP. DAG size: 150 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate)