/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_valuebound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7968f31 [2022-03-17 21:45:11,910 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-17 21:45:11,941 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-17 21:45:11,975 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-17 21:45:11,975 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-17 21:45:11,976 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-17 21:45:11,977 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-17 21:45:11,978 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-17 21:45:11,983 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-17 21:45:11,987 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-17 21:45:11,988 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-17 21:45:11,989 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-17 21:45:11,989 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-17 21:45:11,991 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-17 21:45:11,992 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-17 21:45:11,994 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-17 21:45:11,994 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-17 21:45:11,995 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-17 21:45:11,997 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-17 21:45:12,002 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-17 21:45:12,004 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-17 21:45:12,005 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-17 21:45:12,005 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-17 21:45:12,007 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-17 21:45:12,009 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-17 21:45:12,014 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-17 21:45:12,015 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-17 21:45:12,015 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-17 21:45:12,015 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-17 21:45:12,016 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-17 21:45:12,016 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-17 21:45:12,017 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-17 21:45:12,018 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-17 21:45:12,018 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-17 21:45:12,019 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-17 21:45:12,019 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-17 21:45:12,020 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-17 21:45:12,020 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-17 21:45:12,020 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-17 21:45:12,020 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-17 21:45:12,021 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-17 21:45:12,022 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-17 21:45:12,023 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-03-17 21:45:12,044 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-17 21:45:12,045 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-17 21:45:12,045 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-17 21:45:12,045 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-17 21:45:12,046 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-17 21:45:12,046 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-17 21:45:12,046 INFO L138 SettingsManager]: * Use SBE=true [2022-03-17 21:45:12,046 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-17 21:45:12,046 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-17 21:45:12,047 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-17 21:45:12,047 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-17 21:45:12,047 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-17 21:45:12,047 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-17 21:45:12,047 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-17 21:45:12,047 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-17 21:45:12,047 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-17 21:45:12,048 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-17 21:45:12,048 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-17 21:45:12,048 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-17 21:45:12,048 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 21:45:12,048 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-17 21:45:12,048 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-03-17 21:45:12,048 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-17 21:45:12,048 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-17 21:45:12,048 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-17 21:45:12,049 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-17 21:45:12,049 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-03-17 21:45:12,049 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-03-17 21:45:12,049 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-17 21:45:12,050 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-17 21:45:12,251 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-17 21:45:12,273 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-17 21:45:12,275 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-17 21:45:12,275 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-17 21:45:12,276 INFO L275 PluginConnector]: CDTParser initialized [2022-03-17 21:45:12,277 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound100.c [2022-03-17 21:45:12,321 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/93c4eaf55/4ada02a3624f49b3983a1c195339164a/FLAG1e828c258 [2022-03-17 21:45:12,674 INFO L306 CDTParser]: Found 1 translation units. [2022-03-17 21:45:12,675 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound100.c [2022-03-17 21:45:12,680 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/93c4eaf55/4ada02a3624f49b3983a1c195339164a/FLAG1e828c258 [2022-03-17 21:45:12,689 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/93c4eaf55/4ada02a3624f49b3983a1c195339164a [2022-03-17 21:45:12,690 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-17 21:45:12,691 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-17 21:45:12,692 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-17 21:45:12,692 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-17 21:45:12,695 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-17 21:45:12,695 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 09:45:12" (1/1) ... [2022-03-17 21:45:12,696 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@285b0d5b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:12, skipping insertion in model container [2022-03-17 21:45:12,696 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 09:45:12" (1/1) ... [2022-03-17 21:45:12,700 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-17 21:45:12,710 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-17 21:45:12,831 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_valuebound100.c[538,551] [2022-03-17 21:45:12,845 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 21:45:12,850 INFO L203 MainTranslator]: Completed pre-run [2022-03-17 21:45:12,857 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_valuebound100.c[538,551] [2022-03-17 21:45:12,862 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 21:45:12,871 INFO L208 MainTranslator]: Completed translation [2022-03-17 21:45:12,871 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:12 WrapperNode [2022-03-17 21:45:12,871 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-17 21:45:12,872 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-17 21:45:12,872 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-17 21:45:12,872 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-17 21:45:12,879 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:12" (1/1) ... [2022-03-17 21:45:12,880 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:12" (1/1) ... [2022-03-17 21:45:12,884 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:12" (1/1) ... [2022-03-17 21:45:12,884 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:12" (1/1) ... [2022-03-17 21:45:12,887 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:12" (1/1) ... [2022-03-17 21:45:12,890 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:12" (1/1) ... [2022-03-17 21:45:12,891 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:12" (1/1) ... [2022-03-17 21:45:12,892 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-17 21:45:12,892 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-17 21:45:12,892 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-17 21:45:12,893 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-17 21:45:12,893 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:12" (1/1) ... [2022-03-17 21:45:12,898 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 21:45:12,905 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:45:12,914 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-17 21:45:12,916 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-17 21:45:12,939 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-17 21:45:12,940 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-17 21:45:12,940 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-17 21:45:12,940 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-17 21:45:12,940 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-17 21:45:12,940 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-17 21:45:12,940 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-17 21:45:12,940 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-17 21:45:12,940 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-17 21:45:12,940 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-17 21:45:12,940 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-03-17 21:45:12,940 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-17 21:45:12,941 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-17 21:45:12,941 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-17 21:45:12,941 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-17 21:45:12,941 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-17 21:45:12,941 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-17 21:45:12,941 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-17 21:45:12,941 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-17 21:45:12,941 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-17 21:45:12,982 INFO L234 CfgBuilder]: Building ICFG [2022-03-17 21:45:12,983 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-17 21:45:13,075 INFO L275 CfgBuilder]: Performing block encoding [2022-03-17 21:45:13,079 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-17 21:45:13,079 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-17 21:45:13,080 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 09:45:13 BoogieIcfgContainer [2022-03-17 21:45:13,080 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-17 21:45:13,081 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-17 21:45:13,081 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-17 21:45:13,082 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-17 21:45:13,084 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 09:45:13" (1/1) ... [2022-03-17 21:45:13,097 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 09:45:13 BasicIcfg [2022-03-17 21:45:13,097 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-17 21:45:13,098 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-17 21:45:13,098 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-17 21:45:13,100 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-17 21:45:13,100 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 17.03 09:45:12" (1/4) ... [2022-03-17 21:45:13,100 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@da70c3a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 09:45:13, skipping insertion in model container [2022-03-17 21:45:13,100 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:12" (2/4) ... [2022-03-17 21:45:13,101 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@da70c3a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 09:45:13, skipping insertion in model container [2022-03-17 21:45:13,101 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 09:45:13" (3/4) ... [2022-03-17 21:45:13,101 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@da70c3a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 17.03 09:45:13, skipping insertion in model container [2022-03-17 21:45:13,101 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 09:45:13" (4/4) ... [2022-03-17 21:45:13,102 INFO L111 eAbstractionObserver]: Analyzing ICFG hard-ll_valuebound100.cqvasr [2022-03-17 21:45:13,105 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-03-17 21:45:13,105 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-17 21:45:13,135 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-17 21:45:13,140 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-17 21:45:13,140 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-17 21:45:13,151 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-17 21:45:13,154 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-17 21:45:13,154 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:13,155 INFO L500 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-17 21:45:13,155 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:13,159 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:13,159 INFO L85 PathProgramCache]: Analyzing trace with hash 1011787902, now seen corresponding path program 1 times [2022-03-17 21:45:13,165 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:13,165 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [424426895] [2022-03-17 21:45:13,165 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:13,166 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:13,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:13,326 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-17 21:45:13,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:13,334 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-17 21:45:13,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:13,351 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-17 21:45:13,352 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:13,356 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-17 21:45:13,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:13,371 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-17 21:45:13,372 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:13,372 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [424426895] [2022-03-17 21:45:13,372 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [424426895] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:45:13,373 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:45:13,373 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-17 21:45:13,374 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1466534946] [2022-03-17 21:45:13,374 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:13,377 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-17 21:45:13,377 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:13,399 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-17 21:45:13,400 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-17 21:45:13,402 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-17 21:45:13,503 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:13,503 INFO L93 Difference]: Finished difference Result 69 states and 110 transitions. [2022-03-17 21:45:13,504 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-17 21:45:13,505 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-17 21:45:13,505 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:13,512 INFO L225 Difference]: With dead ends: 69 [2022-03-17 21:45:13,513 INFO L226 Difference]: Without dead ends: 33 [2022-03-17 21:45:13,516 INFO L911 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-17 21:45:13,519 INFO L912 BasicCegarLoop]: 38 mSDtfsCounter, 21 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s 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.1s IncrementalHoareTripleChecker+Time [2022-03-17 21:45:13,520 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 41 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 21:45:13,531 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-03-17 21:45:13,551 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-03-17 21:45:13,552 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-17 21:45:13,555 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2022-03-17 21:45:13,556 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 28 [2022-03-17 21:45:13,556 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:13,557 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2022-03-17 21:45:13,558 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-17 21:45:13,558 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-03-17 21:45:13,559 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-17 21:45:13,559 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:13,560 INFO L500 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-17 21:45:13,560 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-17 21:45:13,560 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:13,568 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:13,568 INFO L85 PathProgramCache]: Analyzing trace with hash -1710049411, now seen corresponding path program 1 times [2022-03-17 21:45:13,568 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:13,569 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [487598292] [2022-03-17 21:45:13,569 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:13,569 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:13,595 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:13,675 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-17 21:45:13,677 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:13,681 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-17 21:45:13,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:13,686 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-17 21:45:13,687 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:13,692 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-17 21:45:13,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:13,699 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-17 21:45:13,699 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:13,700 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [487598292] [2022-03-17 21:45:13,700 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [487598292] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:45:13,700 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:45:13,700 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-17 21:45:13,700 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [206514459] [2022-03-17 21:45:13,701 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:13,702 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-17 21:45:13,702 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:13,703 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-17 21:45:13,703 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-17 21:45:13,704 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-17 21:45:13,883 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:13,884 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-03-17 21:45:13,888 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-17 21:45:13,888 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-17 21:45:13,889 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:13,890 INFO L225 Difference]: With dead ends: 46 [2022-03-17 21:45:13,891 INFO L226 Difference]: Without dead ends: 44 [2022-03-17 21:45:13,894 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-17 21:45:13,895 INFO L912 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.1s IncrementalHoareTripleChecker+Time [2022-03-17 21:45:13,895 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 48 Invalid, 155 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 21:45:13,897 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-03-17 21:45:13,909 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-03-17 21:45:13,909 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-17 21:45:13,911 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 46 transitions. [2022-03-17 21:45:13,911 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 46 transitions. Word has length 28 [2022-03-17 21:45:13,911 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:13,911 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 46 transitions. [2022-03-17 21:45:13,912 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-17 21:45:13,912 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 46 transitions. [2022-03-17 21:45:13,912 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-03-17 21:45:13,913 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:13,913 INFO L500 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-17 21:45:13,913 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-17 21:45:13,913 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:13,914 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:13,914 INFO L85 PathProgramCache]: Analyzing trace with hash 1042498848, now seen corresponding path program 1 times [2022-03-17 21:45:13,914 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:13,914 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1074552909] [2022-03-17 21:45:13,914 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:13,914 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:13,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:14,001 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-17 21:45:14,006 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:14,010 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-17 21:45:14,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:14,013 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-17 21:45:14,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:14,026 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-17 21:45:14,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:14,029 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2022-03-17 21:45:14,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:14,034 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-17 21:45:14,034 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:14,034 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1074552909] [2022-03-17 21:45:14,034 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1074552909] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:45:14,034 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:45:14,034 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-17 21:45:14,035 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [73012125] [2022-03-17 21:45:14,035 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:14,035 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-17 21:45:14,035 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:14,035 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-17 21:45:14,035 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-17 21:45:14,036 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-17 21:45:14,157 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:14,158 INFO L93 Difference]: Finished difference Result 50 states and 63 transitions. [2022-03-17 21:45:14,158 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-17 21:45:14,158 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-17 21:45:14,158 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:14,159 INFO L225 Difference]: With dead ends: 50 [2022-03-17 21:45:14,159 INFO L226 Difference]: Without dead ends: 48 [2022-03-17 21:45:14,159 INFO L911 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-17 21:45:14,160 INFO L912 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-17 21:45:14,160 INFO L913 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-17 21:45:14,161 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-03-17 21:45:14,165 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 41. [2022-03-17 21:45:14,165 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-17 21:45:14,166 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2022-03-17 21:45:14,166 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 33 [2022-03-17 21:45:14,166 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:14,166 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2022-03-17 21:45:14,166 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-17 21:45:14,166 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2022-03-17 21:45:14,167 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-03-17 21:45:14,167 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:14,167 INFO L500 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-17 21:45:14,167 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-03-17 21:45:14,167 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:14,168 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:14,168 INFO L85 PathProgramCache]: Analyzing trace with hash 1436069466, now seen corresponding path program 1 times [2022-03-17 21:45:14,168 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:14,168 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1126159086] [2022-03-17 21:45:14,168 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:14,168 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:14,182 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:45:14,183 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1086451656] [2022-03-17 21:45:14,183 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:14,183 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:14,183 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:45:14,184 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-17 21:45:14,185 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-17 21:45:14,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:14,221 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-17 21:45:14,225 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:45:14,362 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-17 21:45:14,363 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 21:45:14,363 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:14,363 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1126159086] [2022-03-17 21:45:14,363 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:45:14,363 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1086451656] [2022-03-17 21:45:14,363 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1086451656] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:45:14,363 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:45:14,363 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-03-17 21:45:14,364 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1300618024] [2022-03-17 21:45:14,364 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:14,364 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-17 21:45:14,364 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:14,364 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-17 21:45:14,365 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2022-03-17 21:45:14,365 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-17 21:45:14,446 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:14,446 INFO L93 Difference]: Finished difference Result 69 states and 89 transitions. [2022-03-17 21:45:14,446 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-17 21:45:14,446 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-17 21:45:14,446 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:14,447 INFO L225 Difference]: With dead ends: 69 [2022-03-17 21:45:14,447 INFO L226 Difference]: Without dead ends: 55 [2022-03-17 21:45:14,447 INFO L911 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-17 21:45:14,448 INFO L912 BasicCegarLoop]: 40 mSDtfsCounter, 20 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s 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-17 21:45:14,448 INFO L913 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-17 21:45:14,449 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-03-17 21:45:14,454 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-03-17 21:45:14,455 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-17 21:45:14,455 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-03-17 21:45:14,455 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 38 [2022-03-17 21:45:14,456 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:14,456 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-03-17 21:45:14,456 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-17 21:45:14,456 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-03-17 21:45:14,457 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-03-17 21:45:14,457 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:14,457 INFO L500 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-17 21:45:14,498 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-17 21:45:14,674 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-17 21:45:14,675 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:14,675 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:14,675 INFO L85 PathProgramCache]: Analyzing trace with hash 5711864, now seen corresponding path program 1 times [2022-03-17 21:45:14,675 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:14,675 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [33419812] [2022-03-17 21:45:14,675 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:14,675 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:14,682 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:45:14,682 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1176232568] [2022-03-17 21:45:14,682 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:14,682 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:14,683 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:45:14,694 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-17 21:45:14,695 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-17 21:45:14,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:14,731 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-17 21:45:14,733 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:45:14,927 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-17 21:45:14,928 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:45:15,067 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-17 21:45:15,068 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:15,068 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [33419812] [2022-03-17 21:45:15,068 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:45:15,068 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1176232568] [2022-03-17 21:45:15,068 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1176232568] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-17 21:45:15,068 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-17 21:45:15,068 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [9] total 11 [2022-03-17 21:45:15,068 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1279591235] [2022-03-17 21:45:15,068 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:15,069 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-17 21:45:15,069 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:15,069 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-17 21:45:15,069 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-03-17 21:45:15,070 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-17 21:45:15,116 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:15,116 INFO L93 Difference]: Finished difference Result 68 states and 85 transitions. [2022-03-17 21:45:15,116 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 21:45:15,116 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-17 21:45:15,117 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:15,117 INFO L225 Difference]: With dead ends: 68 [2022-03-17 21:45:15,117 INFO L226 Difference]: Without dead ends: 66 [2022-03-17 21:45:15,117 INFO L911 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-17 21:45:15,118 INFO L912 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.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:45:15,118 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 145 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:45:15,119 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-03-17 21:45:15,126 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 64. [2022-03-17 21:45:15,127 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-17 21:45:15,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 80 transitions. [2022-03-17 21:45:15,127 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 80 transitions. Word has length 45 [2022-03-17 21:45:15,128 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:15,128 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 80 transitions. [2022-03-17 21:45:15,128 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-17 21:45:15,128 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 80 transitions. [2022-03-17 21:45:15,129 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-03-17 21:45:15,129 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:15,129 INFO L500 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-17 21:45:15,146 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-17 21:45:15,346 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-17 21:45:15,346 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:15,347 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:15,347 INFO L85 PathProgramCache]: Analyzing trace with hash 1597443315, now seen corresponding path program 1 times [2022-03-17 21:45:15,347 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:15,347 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1977701656] [2022-03-17 21:45:15,348 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:15,348 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:15,355 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:45:15,355 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [297713592] [2022-03-17 21:45:15,356 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:15,356 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:15,356 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:45:15,357 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-17 21:45:15,358 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-17 21:45:15,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:15,394 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 16 conjunts are in the unsatisfiable core [2022-03-17 21:45:15,396 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:45:15,592 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-17 21:45:15,593 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:45:15,697 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-17 21:45:15,698 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:15,698 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1977701656] [2022-03-17 21:45:15,698 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:45:15,698 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [297713592] [2022-03-17 21:45:15,698 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [297713592] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-17 21:45:15,698 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-17 21:45:15,698 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-03-17 21:45:15,698 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1103193110] [2022-03-17 21:45:15,698 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:15,698 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:45:15,698 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:15,699 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:45:15,699 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-03-17 21:45:15,699 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-17 21:45:15,739 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:15,740 INFO L93 Difference]: Finished difference Result 76 states and 95 transitions. [2022-03-17 21:45:15,740 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 21:45:15,740 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-17 21:45:15,740 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:15,741 INFO L225 Difference]: With dead ends: 76 [2022-03-17 21:45:15,741 INFO L226 Difference]: Without dead ends: 74 [2022-03-17 21:45:15,741 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 99 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-03-17 21:45:15,742 INFO L912 BasicCegarLoop]: 41 mSDtfsCounter, 8 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s 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.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:45:15,742 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 141 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:45:15,742 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2022-03-17 21:45:15,749 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2022-03-17 21:45:15,750 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-17 21:45:15,750 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 88 transitions. [2022-03-17 21:45:15,750 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 88 transitions. Word has length 55 [2022-03-17 21:45:15,751 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:15,751 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 88 transitions. [2022-03-17 21:45:15,751 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-17 21:45:15,751 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 88 transitions. [2022-03-17 21:45:15,752 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-03-17 21:45:15,752 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:15,752 INFO L500 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-17 21:45:15,769 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-17 21:45:15,969 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-17 21:45:15,969 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:15,969 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:15,969 INFO L85 PathProgramCache]: Analyzing trace with hash 810354846, now seen corresponding path program 1 times [2022-03-17 21:45:15,969 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:15,969 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [702354449] [2022-03-17 21:45:15,970 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:15,970 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:15,976 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:45:15,976 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1741197570] [2022-03-17 21:45:15,976 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:15,977 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:15,977 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:45:15,978 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-17 21:45:15,980 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-17 21:45:16,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:16,018 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 21:45:16,019 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:45:16,118 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-17 21:45:16,119 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 21:45:16,119 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:16,119 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [702354449] [2022-03-17 21:45:16,119 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:45:16,119 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1741197570] [2022-03-17 21:45:16,119 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1741197570] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:45:16,119 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:45:16,119 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-17 21:45:16,119 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2055808789] [2022-03-17 21:45:16,119 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:16,120 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:45:16,120 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:16,121 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:45:16,121 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-17 21:45:16,121 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-17 21:45:16,160 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:16,160 INFO L93 Difference]: Finished difference Result 79 states and 96 transitions. [2022-03-17 21:45:16,160 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 21:45:16,161 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-17 21:45:16,162 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:16,164 INFO L225 Difference]: With dead ends: 79 [2022-03-17 21:45:16,164 INFO L226 Difference]: Without dead ends: 72 [2022-03-17 21:45:16,164 INFO L911 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-17 21:45:16,165 INFO L912 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-17 21:45:16,165 INFO L913 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-17 21:45:16,167 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2022-03-17 21:45:16,181 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 71. [2022-03-17 21:45:16,181 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-17 21:45:16,182 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 85 transitions. [2022-03-17 21:45:16,182 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 85 transitions. Word has length 56 [2022-03-17 21:45:16,183 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:16,183 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 85 transitions. [2022-03-17 21:45:16,183 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-17 21:45:16,183 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 85 transitions. [2022-03-17 21:45:16,188 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-03-17 21:45:16,188 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:16,188 INFO L500 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-17 21:45:16,204 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2022-03-17 21:45:16,404 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-17 21:45:16,404 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:16,404 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:16,404 INFO L85 PathProgramCache]: Analyzing trace with hash 1689231171, now seen corresponding path program 1 times [2022-03-17 21:45:16,405 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:16,405 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2002293141] [2022-03-17 21:45:16,405 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:16,405 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:16,411 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:45:16,411 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [945282099] [2022-03-17 21:45:16,411 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:16,411 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:16,412 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:45:16,412 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-17 21:45:16,413 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-17 21:45:16,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:16,474 INFO L263 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 30 conjunts are in the unsatisfiable core [2022-03-17 21:45:16,476 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:45:17,058 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-17 21:45:17,059 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:45:57,518 WARN L232 SmtUtils]: Spent 24.41s 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-17 21:46:50,396 WARN L232 SmtUtils]: Spent 15.96s 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-17 21:47:46,205 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-17 21:47:46,205 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:47:46,205 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2002293141] [2022-03-17 21:47:46,205 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:47:46,205 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [945282099] [2022-03-17 21:47:46,206 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [945282099] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:47:46,206 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:47:46,206 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12] total 18 [2022-03-17 21:47:46,206 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [970562790] [2022-03-17 21:47:46,206 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:47:46,206 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-03-17 21:47:46,206 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:47:46,206 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-03-17 21:47:46,207 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=241, Unknown=0, NotChecked=0, Total=306 [2022-03-17 21:47:46,207 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-17 21:47:48,871 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-17 21:48:03,212 WARN L232 SmtUtils]: Spent 14.05s 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-17 21:48:23,987 WARN L232 SmtUtils]: Spent 18.86s 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-17 21:48:26,078 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-17 21:48:33,685 WARN L232 SmtUtils]: Spent 6.14s 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-17 21:48:40,286 WARN L232 SmtUtils]: Spent 5.53s 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-17 21:48:41,815 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:48:41,815 INFO L93 Difference]: Finished difference Result 148 states and 194 transitions. [2022-03-17 21:48:41,816 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2022-03-17 21:48:41,816 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-17 21:48:41,816 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:48:41,817 INFO L225 Difference]: With dead ends: 148 [2022-03-17 21:48:41,817 INFO L226 Difference]: Without dead ends: 121 [2022-03-17 21:48:41,817 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 131 SyntacticMatches, 2 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 111 ImplicationChecksByTransitivity, 87.5s TimeCoverageRelationStatistics Valid=136, Invalid=514, Unknown=0, NotChecked=0, Total=650 [2022-03-17 21:48:41,818 INFO L912 BasicCegarLoop]: 37 mSDtfsCounter, 64 mSDsluCounter, 240 mSDsCounter, 0 mSdLazyCounter, 397 mSolverCounterSat, 142 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 277 SdHoareTripleChecker+Invalid, 541 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 142 IncrementalHoareTripleChecker+Valid, 397 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.5s IncrementalHoareTripleChecker+Time [2022-03-17 21:48:41,818 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [69 Valid, 277 Invalid, 541 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [142 Valid, 397 Invalid, 2 Unknown, 0 Unchecked, 9.5s Time] [2022-03-17 21:48:41,818 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2022-03-17 21:48:41,828 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 103. [2022-03-17 21:48:41,828 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-17 21:48:41,829 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 127 transitions. [2022-03-17 21:48:41,829 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 127 transitions. Word has length 75 [2022-03-17 21:48:41,829 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:48:41,830 INFO L478 AbstractCegarLoop]: Abstraction has 103 states and 127 transitions. [2022-03-17 21:48:41,830 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-17 21:48:41,830 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 127 transitions. [2022-03-17 21:48:41,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2022-03-17 21:48:41,830 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:48:41,831 INFO L500 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-17 21:48:41,847 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-17 21:48:42,031 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-17 21:48:42,031 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:48:42,032 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:48:42,032 INFO L85 PathProgramCache]: Analyzing trace with hash -102783885, now seen corresponding path program 1 times [2022-03-17 21:48:42,032 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:48:42,032 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [143170603] [2022-03-17 21:48:42,032 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:42,032 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:48:42,038 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:48:42,038 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1671134373] [2022-03-17 21:48:42,039 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:42,039 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:42,039 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:48:42,045 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-17 21:48:42,049 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-17 21:48:42,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:48:42,101 INFO L263 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-17 21:48:42,103 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:48:42,319 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-17 21:48:42,320 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:48:42,568 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-17 21:48:42,568 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:48:42,569 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [143170603] [2022-03-17 21:48:42,569 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:48:42,569 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1671134373] [2022-03-17 21:48:42,569 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1671134373] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:48:42,569 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:48:42,569 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2022-03-17 21:48:42,569 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [535579202] [2022-03-17 21:48:42,569 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:48:42,569 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-17 21:48:42,569 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:48:42,570 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-17 21:48:42,570 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2022-03-17 21:48:42,570 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-17 21:48:42,757 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:48:42,757 INFO L93 Difference]: Finished difference Result 116 states and 143 transitions. [2022-03-17 21:48:42,757 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-17 21:48:42,757 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-17 21:48:42,758 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:48:42,759 INFO L225 Difference]: With dead ends: 116 [2022-03-17 21:48:42,759 INFO L226 Difference]: Without dead ends: 114 [2022-03-17 21:48:42,759 INFO L911 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-17 21:48:42,760 INFO L912 BasicCegarLoop]: 44 mSDtfsCounter, 15 mSDsluCounter, 182 mSDsCounter, 0 mSdLazyCounter, 94 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s 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-17 21:48:42,760 INFO L913 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-17 21:48:42,760 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2022-03-17 21:48:42,769 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 107. [2022-03-17 21:48:42,769 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-17 21:48:42,770 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 134 transitions. [2022-03-17 21:48:42,770 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 134 transitions. Word has length 86 [2022-03-17 21:48:42,770 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:48:42,771 INFO L478 AbstractCegarLoop]: Abstraction has 107 states and 134 transitions. [2022-03-17 21:48:42,771 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-17 21:48:42,771 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 134 transitions. [2022-03-17 21:48:42,771 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2022-03-17 21:48:42,771 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:48:42,772 INFO L500 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-17 21:48:42,788 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-17 21:48:42,972 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-17 21:48:42,972 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:48:42,973 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:48:42,973 INFO L85 PathProgramCache]: Analyzing trace with hash 1406960063, now seen corresponding path program 2 times [2022-03-17 21:48:42,973 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:48:42,973 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [390189689] [2022-03-17 21:48:42,973 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:42,973 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:48:42,979 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:48:42,979 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [481266288] [2022-03-17 21:48:42,979 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-17 21:48:42,979 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:42,980 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:48:42,997 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-17 21:48:43,007 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-17 21:48:43,044 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-17 21:48:43,044 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 21:48:43,045 INFO L263 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 21:48:43,047 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:48:43,164 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-17 21:48:43,164 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:48:43,298 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-17 21:48:43,299 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:48:43,299 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [390189689] [2022-03-17 21:48:43,299 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:48:43,299 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [481266288] [2022-03-17 21:48:43,299 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [481266288] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:48:43,299 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:48:43,299 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2022-03-17 21:48:43,299 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2078074053] [2022-03-17 21:48:43,299 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:48:43,299 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:48:43,299 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:48:43,300 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:48:43,300 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-17 21:48:43,300 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-17 21:48:43,365 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:48:43,365 INFO L93 Difference]: Finished difference Result 130 states and 164 transitions. [2022-03-17 21:48:43,365 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-03-17 21:48:43,366 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-17 21:48:43,366 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:48:43,367 INFO L225 Difference]: With dead ends: 130 [2022-03-17 21:48:43,367 INFO L226 Difference]: Without dead ends: 111 [2022-03-17 21:48:43,367 INFO L911 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-17 21:48:43,368 INFO L912 BasicCegarLoop]: 56 mSDtfsCounter, 1 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s 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-17 21:48:43,368 INFO L913 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-17 21:48:43,368 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2022-03-17 21:48:43,378 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 111. [2022-03-17 21:48:43,378 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-17 21:48:43,379 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 140 transitions. [2022-03-17 21:48:43,379 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 140 transitions. Word has length 88 [2022-03-17 21:48:43,379 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:48:43,379 INFO L478 AbstractCegarLoop]: Abstraction has 111 states and 140 transitions. [2022-03-17 21:48:43,379 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-17 21:48:43,380 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 140 transitions. [2022-03-17 21:48:43,380 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-03-17 21:48:43,380 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:48:43,380 INFO L500 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-17 21:48:43,397 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-17 21:48:43,597 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-17 21:48:43,597 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:48:43,597 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:48:43,598 INFO L85 PathProgramCache]: Analyzing trace with hash 966352941, now seen corresponding path program 1 times [2022-03-17 21:48:43,598 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:48:43,598 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [820536844] [2022-03-17 21:48:43,598 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:43,598 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:48:43,603 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:48:43,603 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1520586959] [2022-03-17 21:48:43,603 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:43,604 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:43,604 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:48:43,613 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-17 21:48:43,615 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-17 21:48:43,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:48:43,650 INFO L263 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-17 21:48:43,652 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:48:43,853 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-17 21:48:43,853 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:48:44,143 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-17 21:48:44,143 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:48:44,143 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [820536844] [2022-03-17 21:48:44,143 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:48:44,143 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1520586959] [2022-03-17 21:48:44,143 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1520586959] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:48:44,143 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:48:44,143 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2022-03-17 21:48:44,143 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [617767822] [2022-03-17 21:48:44,144 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:48:44,144 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-17 21:48:44,144 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:48:44,144 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-17 21:48:44,144 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-03-17 21:48:44,145 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-17 21:48:44,383 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:48:44,383 INFO L93 Difference]: Finished difference Result 119 states and 148 transitions. [2022-03-17 21:48:44,384 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-17 21:48:44,384 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-17 21:48:44,384 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:48:44,385 INFO L225 Difference]: With dead ends: 119 [2022-03-17 21:48:44,385 INFO L226 Difference]: Without dead ends: 102 [2022-03-17 21:48:44,385 INFO L911 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-17 21:48:44,385 INFO L912 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-17 21:48:44,386 INFO L913 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-17 21:48:44,386 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2022-03-17 21:48:44,408 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 102. [2022-03-17 21:48:44,408 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-17 21:48:44,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 126 transitions. [2022-03-17 21:48:44,409 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 126 transitions. Word has length 91 [2022-03-17 21:48:44,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:48:44,409 INFO L478 AbstractCegarLoop]: Abstraction has 102 states and 126 transitions. [2022-03-17 21:48:44,409 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-17 21:48:44,409 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 126 transitions. [2022-03-17 21:48:44,410 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2022-03-17 21:48:44,410 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:48:44,410 INFO L500 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-17 21:48:44,426 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-17 21:48:44,611 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-17 21:48:44,611 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:48:44,611 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:48:44,611 INFO L85 PathProgramCache]: Analyzing trace with hash -1871497790, now seen corresponding path program 1 times [2022-03-17 21:48:44,611 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:48:44,611 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [999184525] [2022-03-17 21:48:44,611 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:44,612 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:48:44,617 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:48:44,618 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1896109478] [2022-03-17 21:48:44,618 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:44,618 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:44,618 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:48:44,626 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-17 21:48:44,627 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-17 21:48:44,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:48:44,666 INFO L263 TraceCheckSpWp]: Trace formula consists of 212 conjuncts, 4 conjunts are in the unsatisfiable core [2022-03-17 21:48:44,667 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:48:44,841 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-17 21:48:44,841 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 21:48:44,841 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:48:44,841 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [999184525] [2022-03-17 21:48:44,841 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:48:44,841 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1896109478] [2022-03-17 21:48:44,841 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1896109478] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:48:44,841 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:48:44,841 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-17 21:48:44,842 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [390555928] [2022-03-17 21:48:44,842 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:48:44,842 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:48:44,842 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:48:44,842 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:48:44,842 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-03-17 21:48:44,842 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-17 21:48:44,910 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:48:44,910 INFO L93 Difference]: Finished difference Result 116 states and 141 transitions. [2022-03-17 21:48:44,910 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 21:48:44,911 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-17 21:48:44,911 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:48:44,911 INFO L225 Difference]: With dead ends: 116 [2022-03-17 21:48:44,911 INFO L226 Difference]: Without dead ends: 104 [2022-03-17 21:48:44,912 INFO L911 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-17 21:48:44,912 INFO L912 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-17 21:48:44,912 INFO L913 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-17 21:48:44,912 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2022-03-17 21:48:44,920 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 104. [2022-03-17 21:48:44,920 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-17 21:48:44,921 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 127 transitions. [2022-03-17 21:48:44,921 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 127 transitions. Word has length 95 [2022-03-17 21:48:44,921 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:48:44,921 INFO L478 AbstractCegarLoop]: Abstraction has 104 states and 127 transitions. [2022-03-17 21:48:44,921 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-17 21:48:44,921 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 127 transitions. [2022-03-17 21:48:44,922 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2022-03-17 21:48:44,922 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:48:44,922 INFO L500 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-17 21:48:44,938 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2022-03-17 21:48:45,135 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-17 21:48:45,135 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:48:45,136 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:48:45,136 INFO L85 PathProgramCache]: Analyzing trace with hash -317970408, now seen corresponding path program 3 times [2022-03-17 21:48:45,136 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:48:45,136 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1221837204] [2022-03-17 21:48:45,136 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:45,136 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:48:45,142 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:48:45,142 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1980699285] [2022-03-17 21:48:45,142 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-17 21:48:45,142 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:45,142 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:48:45,150 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-17 21:48:45,153 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-17 21:48:45,206 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-17 21:48:45,206 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 21:48:45,207 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 45 conjunts are in the unsatisfiable core [2022-03-17 21:48:45,209 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:48:45,766 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-17 21:48:45,766 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:49:33,035 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 31 proven. 55 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2022-03-17 21:49:33,035 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:49:33,035 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1221837204] [2022-03-17 21:49:33,035 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:49:33,036 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1980699285] [2022-03-17 21:49:33,036 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1980699285] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:49:33,036 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:49:33,036 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 23 [2022-03-17 21:49:33,036 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [34032853] [2022-03-17 21:49:33,036 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:49:33,036 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-03-17 21:49:33,036 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:49:33,036 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-03-17 21:49:33,037 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=419, Unknown=2, NotChecked=0, Total=506 [2022-03-17 21:49:33,037 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-17 21:50:44,904 WARN L232 SmtUtils]: Spent 1.17m 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-17 21:50:46,395 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.49s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 21:50:48,675 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-17 21:53:04,219 WARN L232 SmtUtils]: Spent 2.24m 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-17 21:53:06,562 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-17 21:53:08,566 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-17 21:54:17,166 WARN L232 SmtUtils]: Spent 1.14m 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-17 21:54:19,426 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-17 21:54:25,163 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.37s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 21:54:27,366 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-17 21:54:29,369 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-17 21:54:31,372 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-17 21:55:58,887 WARN L232 SmtUtils]: Spent 1.41m 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-17 21:56:15,386 WARN L232 SmtUtils]: Spent 13.63s 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-17 21:56:16,659 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.27s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 21:56:22,847 WARN L232 SmtUtils]: Spent 5.03s 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-17 21:56:26,413 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.60s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 21:56:28,420 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-17 21:56:30,643 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.95s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 21:56:34,429 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-17 21:56:37,493 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-17 21:56:40,212 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 21:56:42,791 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.27s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 21:56:44,823 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-17 21:56:46,602 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.76s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 21:56:46,836 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:56:46,836 INFO L93 Difference]: Finished difference Result 238 states and 312 transitions. [2022-03-17 21:56:46,837 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2022-03-17 21:56:46,837 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-17 21:56:46,837 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:56:46,838 INFO L225 Difference]: With dead ends: 238 [2022-03-17 21:56:46,838 INFO L226 Difference]: Without dead ends: 185 [2022-03-17 21:56:46,840 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 227 GetRequests, 184 SyntacticMatches, 4 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 334 ImplicationChecksByTransitivity, 398.8s TimeCoverageRelationStatistics Valid=282, Invalid=1356, Unknown=2, NotChecked=0, Total=1640 [2022-03-17 21:56:46,841 INFO L912 BasicCegarLoop]: 50 mSDtfsCounter, 150 mSDsluCounter, 421 mSDsCounter, 0 mSdLazyCounter, 858 mSolverCounterSat, 359 mSolverCounterUnsat, 12 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 45.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 163 SdHoareTripleChecker+Valid, 471 SdHoareTripleChecker+Invalid, 1229 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 359 IncrementalHoareTripleChecker+Valid, 858 IncrementalHoareTripleChecker+Invalid, 12 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 46.1s IncrementalHoareTripleChecker+Time [2022-03-17 21:56:46,841 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [163 Valid, 471 Invalid, 1229 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [359 Valid, 858 Invalid, 12 Unknown, 0 Unchecked, 46.1s Time] [2022-03-17 21:56:46,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 185 states. [2022-03-17 21:56:46,856 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 185 to 165. [2022-03-17 21:56:46,857 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 165 states, 97 states have (on average 1.1237113402061856) internal successors, (109), 105 states have internal predecessors, (109), 49 states have call successors, (49), 19 states have call predecessors, (49), 18 states have return successors, (47), 40 states have call predecessors, (47), 47 states have call successors, (47) [2022-03-17 21:56:46,858 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 205 transitions. [2022-03-17 21:56:46,858 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 205 transitions. Word has length 105 [2022-03-17 21:56:46,858 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:56:46,858 INFO L478 AbstractCegarLoop]: Abstraction has 165 states and 205 transitions. [2022-03-17 21:56:46,858 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-17 21:56:46,858 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 205 transitions. [2022-03-17 21:56:46,859 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2022-03-17 21:56:46,859 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:56:46,859 INFO L500 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-17 21:56:46,891 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-17 21:56:47,077 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-17 21:56:47,077 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:56:47,077 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:56:47,077 INFO L85 PathProgramCache]: Analyzing trace with hash -1498631042, now seen corresponding path program 2 times [2022-03-17 21:56:47,077 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:56:47,078 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [659895511] [2022-03-17 21:56:47,078 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:56:47,078 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:56:47,084 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:56:47,084 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [935768444] [2022-03-17 21:56:47,084 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-17 21:56:47,084 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:56:47,084 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:56:47,085 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-17 21:56:47,086 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-17 21:56:47,190 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-17 21:56:47,190 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 21:56:47,192 INFO L263 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 49 conjunts are in the unsatisfiable core [2022-03-17 21:56:47,194 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:56:48,073 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-17 21:56:48,786 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-17 21:56:48,787 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:56:49,265 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-17 21:56:49,265 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:56:49,265 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [659895511] [2022-03-17 21:56:49,265 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:56:49,265 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [935768444] [2022-03-17 21:56:49,266 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [935768444] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:56:49,266 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:56:49,266 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 9] total 20 [2022-03-17 21:56:49,266 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [483531414] [2022-03-17 21:56:49,266 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:56:49,266 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-03-17 21:56:49,266 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:56:49,267 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-03-17 21:56:49,267 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=302, Unknown=0, NotChecked=0, Total=380 [2022-03-17 21:56:49,267 INFO L87 Difference]: Start difference. First operand 165 states and 205 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-17 21:56:50,279 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:56:50,280 INFO L93 Difference]: Finished difference Result 232 states and 280 transitions. [2022-03-17 21:56:50,280 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-03-17 21:56:50,280 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-17 21:56:50,281 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:56:50,281 INFO L225 Difference]: With dead ends: 232 [2022-03-17 21:56:50,281 INFO L226 Difference]: Without dead ends: 163 [2022-03-17 21:56:50,282 INFO L911 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-17 21:56:50,282 INFO L912 BasicCegarLoop]: 45 mSDtfsCounter, 45 mSDsluCounter, 307 mSDsCounter, 0 mSdLazyCounter, 451 mSolverCounterSat, 110 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 352 SdHoareTripleChecker+Invalid, 561 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 110 IncrementalHoareTripleChecker+Valid, 451 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:56:50,282 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [58 Valid, 352 Invalid, 561 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [110 Valid, 451 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2022-03-17 21:56:50,283 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states. [2022-03-17 21:56:50,295 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 146. [2022-03-17 21:56:50,296 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 146 states, 88 states have (on average 1.1022727272727273) internal successors, (97), 94 states have internal predecessors, (97), 38 states have call successors, (38), 20 states have call predecessors, (38), 19 states have return successors, (36), 31 states have call predecessors, (36), 36 states have call successors, (36) [2022-03-17 21:56:50,296 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 171 transitions. [2022-03-17 21:56:50,296 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 171 transitions. Word has length 116 [2022-03-17 21:56:50,297 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:56:50,297 INFO L478 AbstractCegarLoop]: Abstraction has 146 states and 171 transitions. [2022-03-17 21:56:50,297 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-17 21:56:50,297 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 171 transitions. [2022-03-17 21:56:50,297 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2022-03-17 21:56:50,297 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:56:50,298 INFO L500 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-17 21:56:50,314 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2022-03-17 21:56:50,511 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-17 21:56:50,511 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:56:50,512 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:56:50,512 INFO L85 PathProgramCache]: Analyzing trace with hash -715358301, now seen corresponding path program 4 times [2022-03-17 21:56:50,512 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:56:50,512 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1254473727] [2022-03-17 21:56:50,512 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:56:50,512 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:56:50,521 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:56:50,521 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [134069348] [2022-03-17 21:56:50,521 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-17 21:56:50,521 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:56:50,521 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:56:50,538 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-17 21:56:50,538 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-17 21:56:50,603 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-17 21:56:50,604 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 21:56:50,605 INFO L263 TraceCheckSpWp]: Trace formula consists of 303 conjuncts, 51 conjunts are in the unsatisfiable core [2022-03-17 21:56:50,607 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:56:51,497 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-17 21:56:51,498 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:57:10,995 WARN L232 SmtUtils]: Spent 5.01s on a formula simplification that was a NOOP. DAG size: 147 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 21:57:43,927 WARN L232 SmtUtils]: Spent 6.62s 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) [2022-03-17 21:59:01,272 WARN L232 SmtUtils]: Spent 33.55s on a formula simplification that was a NOOP. DAG size: 451 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate)