/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/egcd2-ll_valuebound10.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 11:50:07,139 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 11:50:07,142 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 11:50:07,173 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 11:50:07,173 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 11:50:07,174 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 11:50:07,181 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 11:50:07,187 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 11:50:07,189 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 11:50:07,193 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 11:50:07,194 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 11:50:07,195 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 11:50:07,196 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 11:50:07,198 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 11:50:07,199 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 11:50:07,201 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 11:50:07,201 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 11:50:07,202 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 11:50:07,206 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 11:50:07,212 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 11:50:07,213 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 11:50:07,214 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 11:50:07,215 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 11:50:07,215 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 11:50:07,217 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 11:50:07,222 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 11:50:07,223 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 11:50:07,223 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 11:50:07,224 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 11:50:07,224 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 11:50:07,225 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 11:50:07,225 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 11:50:07,227 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 11:50:07,228 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 11:50:07,228 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 11:50:07,229 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 11:50:07,229 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 11:50:07,230 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 11:50:07,230 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 11:50:07,230 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 11:50:07,231 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 11:50:07,232 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 11:50:07,233 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-04-06 11:50:07,261 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 11:50:07,262 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 11:50:07,263 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-06 11:50:07,263 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-06 11:50:07,263 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-06 11:50:07,264 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-06 11:50:07,264 INFO L138 SettingsManager]: * Use SBE=true [2022-04-06 11:50:07,264 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 11:50:07,264 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 11:50:07,264 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 11:50:07,264 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 11:50:07,264 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 11:50:07,264 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 11:50:07,264 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 11:50:07,265 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 11:50:07,265 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 11:50:07,265 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 11:50:07,265 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 11:50:07,265 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 11:50:07,265 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 11:50:07,265 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 11:50:07,265 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-06 11:50:07,265 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-06 11:50:07,265 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-06 11:50:07,266 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-06 11:50:07,266 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-06 11:50:07,266 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-04-06 11:50:07,266 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-04-06 11:50:07,266 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-06 11:50:07,266 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-04-06 11:50:07,501 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 11:50:07,521 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 11:50:07,523 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 11:50:07,524 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 11:50:07,526 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 11:50:07,527 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound10.c [2022-04-06 11:50:07,591 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7f66fbce1/724731b506e94cb985ad433e1cf60635/FLAG60c83d2f2 [2022-04-06 11:50:07,977 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 11:50:07,977 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound10.c [2022-04-06 11:50:07,984 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7f66fbce1/724731b506e94cb985ad433e1cf60635/FLAG60c83d2f2 [2022-04-06 11:50:08,404 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7f66fbce1/724731b506e94cb985ad433e1cf60635 [2022-04-06 11:50:08,406 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 11:50:08,407 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-06 11:50:08,408 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 11:50:08,408 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 11:50:08,412 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 11:50:08,413 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 11:50:08" (1/1) ... [2022-04-06 11:50:08,414 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@198fcd77 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:50:08, skipping insertion in model container [2022-04-06 11:50:08,414 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 11:50:08" (1/1) ... [2022-04-06 11:50:08,421 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 11:50:08,444 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 11:50:08,582 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/egcd2-ll_valuebound10.c[490,503] [2022-04-06 11:50:08,600 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 11:50:08,608 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 11:50:08,618 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/egcd2-ll_valuebound10.c[490,503] [2022-04-06 11:50:08,627 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 11:50:08,637 INFO L208 MainTranslator]: Completed translation [2022-04-06 11:50:08,638 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:50:08 WrapperNode [2022-04-06 11:50:08,638 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 11:50:08,639 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 11:50:08,639 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 11:50:08,640 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 11:50:08,648 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:50:08" (1/1) ... [2022-04-06 11:50:08,648 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:50:08" (1/1) ... [2022-04-06 11:50:08,654 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:50:08" (1/1) ... [2022-04-06 11:50:08,654 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:50:08" (1/1) ... [2022-04-06 11:50:08,659 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:50:08" (1/1) ... [2022-04-06 11:50:08,662 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:50:08" (1/1) ... [2022-04-06 11:50:08,664 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:50:08" (1/1) ... [2022-04-06 11:50:08,666 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 11:50:08,666 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 11:50:08,667 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 11:50:08,667 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 11:50:08,667 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:50:08" (1/1) ... [2022-04-06 11:50:08,673 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 11:50:08,682 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:08,696 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-04-06 11:50:08,716 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-04-06 11:50:08,734 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 11:50:08,734 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 11:50:08,734 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 11:50:08,734 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 11:50:08,734 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 11:50:08,734 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 11:50:08,735 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 11:50:08,735 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 11:50:08,735 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 11:50:08,735 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 11:50:08,735 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-06 11:50:08,735 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 11:50:08,735 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 11:50:08,735 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 11:50:08,735 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 11:50:08,736 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 11:50:08,736 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 11:50:08,736 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 11:50:08,736 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 11:50:08,736 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 11:50:08,795 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 11:50:08,796 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 11:50:08,924 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 11:50:08,929 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 11:50:08,930 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-06 11:50:08,931 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:50:08 BoogieIcfgContainer [2022-04-06 11:50:08,932 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 11:50:08,932 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-06 11:50:08,932 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-06 11:50:08,933 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-06 11:50:08,936 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:50:08" (1/1) ... [2022-04-06 11:50:08,938 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_QVASR [2022-04-06 11:50:08,954 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 11:50:08 BasicIcfg [2022-04-06 11:50:08,954 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-06 11:50:08,966 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 11:50:08,966 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 11:50:08,969 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 11:50:08,969 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 11:50:08" (1/4) ... [2022-04-06 11:50:08,970 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@14e529e0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 11:50:08, skipping insertion in model container [2022-04-06 11:50:08,970 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:50:08" (2/4) ... [2022-04-06 11:50:08,970 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@14e529e0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 11:50:08, skipping insertion in model container [2022-04-06 11:50:08,970 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:50:08" (3/4) ... [2022-04-06 11:50:08,970 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@14e529e0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 11:50:08, skipping insertion in model container [2022-04-06 11:50:08,971 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 11:50:08" (4/4) ... [2022-04-06 11:50:08,971 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll_valuebound10.cqvasr [2022-04-06 11:50:08,976 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-06 11:50:08,976 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 11:50:09,053 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 11:50:09,070 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-04-06 11:50:09,070 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 11:50:09,093 INFO L276 IsEmpty]: Start isEmpty. Operand has 40 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-06 11:50:09,098 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-04-06 11:50:09,098 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:09,099 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 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-04-06 11:50:09,099 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:09,107 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:09,107 INFO L85 PathProgramCache]: Analyzing trace with hash -1630657446, now seen corresponding path program 1 times [2022-04-06 11:50:09,113 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:09,114 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1680031212] [2022-04-06 11:50:09,114 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:09,114 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:09,193 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:09,241 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 11:50:09,245 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:09,252 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 11:50:09,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:09,258 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-06 11:50:09,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:09,265 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-06 11:50:09,267 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:09,272 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-04-06 11:50:09,274 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:09,279 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2022-04-06 11:50:09,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:09,286 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2022-04-06 11:50:09,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:09,293 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-06 11:50:09,293 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:09,293 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1680031212] [2022-04-06 11:50:09,294 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1680031212] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 11:50:09,294 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 11:50:09,294 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 11:50:09,296 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [287285933] [2022-04-06 11:50:09,296 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 11:50:09,300 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 11:50:09,300 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:09,322 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 11:50:09,323 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 11:50:09,325 INFO L87 Difference]: Start difference. First operand has 40 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) 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, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 11:50:09,441 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:09,442 INFO L93 Difference]: Finished difference Result 73 states and 118 transitions. [2022-04-06 11:50:09,444 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 11:50:09,445 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, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 43 [2022-04-06 11:50:09,446 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:09,454 INFO L225 Difference]: With dead ends: 73 [2022-04-06 11:50:09,454 INFO L226 Difference]: Without dead ends: 35 [2022-04-06 11:50:09,458 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 21 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-04-06 11:50:09,462 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 11:50:09,469 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 42 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 11:50:09,491 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-04-06 11:50:09,523 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2022-04-06 11:50:09,524 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 11:50:09,528 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 46 transitions. [2022-04-06 11:50:09,530 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 46 transitions. Word has length 43 [2022-04-06 11:50:09,531 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:09,531 INFO L478 AbstractCegarLoop]: Abstraction has 35 states and 46 transitions. [2022-04-06 11:50:09,532 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, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 11:50:09,532 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 46 transitions. [2022-04-06 11:50:09,534 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-04-06 11:50:09,534 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:09,535 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 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-04-06 11:50:09,537 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 11:50:09,537 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:09,538 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:09,538 INFO L85 PathProgramCache]: Analyzing trace with hash -1790145708, now seen corresponding path program 1 times [2022-04-06 11:50:09,538 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:09,538 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1182020477] [2022-04-06 11:50:09,538 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:09,538 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:09,558 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:09,559 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1389578487] [2022-04-06 11:50:09,559 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:09,559 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:09,560 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:09,561 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-04-06 11:50:09,562 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-04-06 11:50:09,637 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:09,639 INFO L263 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 11:50:09,646 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:09,862 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-06 11:50:09,862 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:50:10,015 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-06 11:50:10,017 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:10,017 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1182020477] [2022-04-06 11:50:10,020 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:50:10,021 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1389578487] [2022-04-06 11:50:10,024 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1389578487] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:50:10,024 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:50:10,024 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2022-04-06 11:50:10,025 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [620048395] [2022-04-06 11:50:10,025 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:50:10,026 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-06 11:50:10,026 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:10,026 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-06 11:50:10,026 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-06 11:50:10,027 INFO L87 Difference]: Start difference. First operand 35 states and 46 transitions. Second operand has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 11:50:10,162 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:10,162 INFO L93 Difference]: Finished difference Result 52 states and 69 transitions. [2022-04-06 11:50:10,162 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 11:50:10,163 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 44 [2022-04-06 11:50:10,163 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:10,164 INFO L225 Difference]: With dead ends: 52 [2022-04-06 11:50:10,164 INFO L226 Difference]: Without dead ends: 44 [2022-04-06 11:50:10,164 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 81 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-04-06 11:50:10,165 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 19 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 113 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 124 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 113 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 11:50:10,166 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 152 Invalid, 124 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 113 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 11:50:10,167 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-06 11:50:10,174 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-04-06 11:50:10,175 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 19 states have (on average 1.1578947368421053) internal successors, (22), 20 states have internal predecessors, (22), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 11:50:10,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 48 transitions. [2022-04-06 11:50:10,176 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 48 transitions. Word has length 44 [2022-04-06 11:50:10,176 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:10,176 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 48 transitions. [2022-04-06 11:50:10,177 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 11:50:10,177 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 48 transitions. [2022-04-06 11:50:10,178 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-04-06 11:50:10,178 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:10,178 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 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-04-06 11:50:10,206 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-04-06 11:50:10,393 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:10,394 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:10,394 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:10,394 INFO L85 PathProgramCache]: Analyzing trace with hash 375385207, now seen corresponding path program 1 times [2022-04-06 11:50:10,394 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:10,394 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1541368302] [2022-04-06 11:50:10,395 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:10,395 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:10,424 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:10,425 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [528553770] [2022-04-06 11:50:10,425 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:10,425 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:10,425 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:10,429 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-04-06 11:50:10,432 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-04-06 11:50:10,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:10,490 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-06 11:50:10,498 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:10,669 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-06 11:50:10,669 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:50:10,809 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-06 11:50:10,810 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:10,810 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1541368302] [2022-04-06 11:50:10,810 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:50:10,810 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [528553770] [2022-04-06 11:50:10,810 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [528553770] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 11:50:10,811 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 11:50:10,811 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-04-06 11:50:10,811 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [73230777] [2022-04-06 11:50:10,811 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 11:50:10,812 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 11:50:10,812 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:10,812 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 11:50:10,812 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2022-04-06 11:50:10,812 INFO L87 Difference]: Start difference. First operand 37 states and 48 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2022-04-06 11:50:10,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:10,858 INFO L93 Difference]: Finished difference Result 43 states and 53 transitions. [2022-04-06 11:50:10,858 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 11:50:10,858 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) Word has length 45 [2022-04-06 11:50:10,858 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:10,859 INFO L225 Difference]: With dead ends: 43 [2022-04-06 11:50:10,859 INFO L226 Difference]: Without dead ends: 41 [2022-04-06 11:50:10,860 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 80 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-04-06 11:50:10,861 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 137 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-04-06 11:50:10,861 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 137 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 11:50:10,862 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-04-06 11:50:10,867 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-04-06 11:50:10,868 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 23 states have internal predecessors, (25), 14 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 11:50:10,869 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 51 transitions. [2022-04-06 11:50:10,869 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 51 transitions. Word has length 45 [2022-04-06 11:50:10,869 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:10,869 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 51 transitions. [2022-04-06 11:50:10,869 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2022-04-06 11:50:10,870 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 51 transitions. [2022-04-06 11:50:10,871 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-04-06 11:50:10,871 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:10,871 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:50:10,900 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-04-06 11:50:11,087 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-04-06 11:50:11,088 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:11,088 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:11,088 INFO L85 PathProgramCache]: Analyzing trace with hash -788787523, now seen corresponding path program 1 times [2022-04-06 11:50:11,089 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:11,089 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [384144557] [2022-04-06 11:50:11,089 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:11,089 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:11,105 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:11,105 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1217173260] [2022-04-06 11:50:11,105 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:11,105 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:11,106 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:11,108 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-04-06 11:50:11,110 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-04-06 11:50:11,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:11,159 INFO L263 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-06 11:50:11,162 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:11,385 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 7 proven. 10 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-06 11:50:11,385 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:50:11,468 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:11,468 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [384144557] [2022-04-06 11:50:11,468 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:50:11,468 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1217173260] [2022-04-06 11:50:11,468 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1217173260] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 11:50:11,469 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 11:50:11,469 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-04-06 11:50:11,469 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1882796436] [2022-04-06 11:50:11,469 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-06 11:50:11,469 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-06 11:50:11,470 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:11,470 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-06 11:50:11,470 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2022-04-06 11:50:11,470 INFO L87 Difference]: Start difference. First operand 41 states and 51 transitions. Second operand has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-06 11:50:11,651 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:11,651 INFO L93 Difference]: Finished difference Result 54 states and 68 transitions. [2022-04-06 11:50:11,652 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 11:50:11,654 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 50 [2022-04-06 11:50:11,656 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:11,657 INFO L225 Difference]: With dead ends: 54 [2022-04-06 11:50:11,658 INFO L226 Difference]: Without dead ends: 52 [2022-04-06 11:50:11,658 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 44 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2022-04-06 11:50:11,662 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 26 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 225 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 168 SdHoareTripleChecker+Invalid, 233 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 225 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 11:50:11,663 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 168 Invalid, 233 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 225 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 11:50:11,664 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-06 11:50:11,680 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 51. [2022-04-06 11:50:11,680 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 28 states have internal predecessors, (31), 18 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-06 11:50:11,687 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 65 transitions. [2022-04-06 11:50:11,687 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 65 transitions. Word has length 50 [2022-04-06 11:50:11,688 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:11,688 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 65 transitions. [2022-04-06 11:50:11,688 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-06 11:50:11,689 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 65 transitions. [2022-04-06 11:50:11,694 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-04-06 11:50:11,694 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:11,694 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:50:11,726 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-04-06 11:50:11,919 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:11,920 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:11,920 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:11,920 INFO L85 PathProgramCache]: Analyzing trace with hash -735644649, now seen corresponding path program 1 times [2022-04-06 11:50:11,920 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:11,920 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1804583557] [2022-04-06 11:50:11,921 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:11,921 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:11,932 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:11,933 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1674603147] [2022-04-06 11:50:11,933 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:11,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:11,933 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:11,934 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-04-06 11:50:11,936 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-04-06 11:50:11,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:11,978 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-06 11:50:11,980 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:12,239 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 7 proven. 21 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-06 11:50:12,239 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:50:12,413 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-04-06 11:50:12,413 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:12,413 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1804583557] [2022-04-06 11:50:12,413 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:50:12,414 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1674603147] [2022-04-06 11:50:12,414 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1674603147] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 11:50:12,414 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 11:50:12,414 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-04-06 11:50:12,414 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [532506995] [2022-04-06 11:50:12,414 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 11:50:12,415 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 11:50:12,415 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:12,415 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 11:50:12,415 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-04-06 11:50:12,416 INFO L87 Difference]: Start difference. First operand 51 states and 65 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 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-04-06 11:50:12,476 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:12,477 INFO L93 Difference]: Finished difference Result 58 states and 71 transitions. [2022-04-06 11:50:12,477 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 11:50:12,477 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 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 55 [2022-04-06 11:50:12,478 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:12,478 INFO L225 Difference]: With dead ends: 58 [2022-04-06 11:50:12,479 INFO L226 Difference]: Without dead ends: 56 [2022-04-06 11:50:12,479 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 100 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-04-06 11:50:12,480 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 7 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 11:50:12,480 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 149 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 11:50:12,480 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2022-04-06 11:50:12,488 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2022-04-06 11:50:12,489 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 31 states have internal predecessors, (34), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-06 11:50:12,489 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-04-06 11:50:12,489 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 55 [2022-04-06 11:50:12,490 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:12,490 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-04-06 11:50:12,490 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 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-04-06 11:50:12,490 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-04-06 11:50:12,491 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2022-04-06 11:50:12,491 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:12,491 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:50:12,518 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-06 11:50:12,704 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:12,705 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:12,705 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:12,705 INFO L85 PathProgramCache]: Analyzing trace with hash -1700404515, now seen corresponding path program 1 times [2022-04-06 11:50:12,705 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:12,705 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [760499253] [2022-04-06 11:50:12,706 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:12,706 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:12,718 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:12,718 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1649399593] [2022-04-06 11:50:12,723 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:12,723 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:12,724 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:12,724 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-04-06 11:50:12,748 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-04-06 11:50:12,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:12,774 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 23 conjunts are in the unsatisfiable core [2022-04-06 11:50:12,777 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:12,986 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2022-04-06 11:50:12,986 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:50:13,071 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:13,072 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [760499253] [2022-04-06 11:50:13,072 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:50:13,072 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1649399593] [2022-04-06 11:50:13,072 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1649399593] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 11:50:13,072 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 11:50:13,072 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-04-06 11:50:13,072 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1332041676] [2022-04-06 11:50:13,072 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-06 11:50:13,073 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-06 11:50:13,073 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:13,073 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-06 11:50:13,073 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2022-04-06 11:50:13,074 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-04-06 11:50:13,178 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:13,178 INFO L93 Difference]: Finished difference Result 62 states and 74 transitions. [2022-04-06 11:50:13,178 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 11:50:13,179 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 60 [2022-04-06 11:50:13,179 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:13,180 INFO L225 Difference]: With dead ends: 62 [2022-04-06 11:50:13,180 INFO L226 Difference]: Without dead ends: 60 [2022-04-06 11:50:13,180 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 56 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2022-04-06 11:50:13,181 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 12 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 106 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 106 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 11:50:13,181 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 138 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 11:50:13,182 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2022-04-06 11:50:13,188 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2022-04-06 11:50:13,189 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 33 states have (on average 1.121212121212121) internal successors, (37), 34 states have internal predecessors, (37), 18 states have call successors, (18), 8 states have call predecessors, (18), 7 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-06 11:50:13,189 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 71 transitions. [2022-04-06 11:50:13,189 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 71 transitions. Word has length 60 [2022-04-06 11:50:13,190 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:13,190 INFO L478 AbstractCegarLoop]: Abstraction has 59 states and 71 transitions. [2022-04-06 11:50:13,190 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-04-06 11:50:13,190 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 71 transitions. [2022-04-06 11:50:13,191 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2022-04-06 11:50:13,191 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:13,191 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:50:13,219 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-04-06 11:50:13,416 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:13,416 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:13,417 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:13,417 INFO L85 PathProgramCache]: Analyzing trace with hash 2004479621, now seen corresponding path program 1 times [2022-04-06 11:50:13,417 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:13,417 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [642323515] [2022-04-06 11:50:13,417 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:13,417 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:13,439 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:13,440 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2109650674] [2022-04-06 11:50:13,440 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:13,440 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:13,440 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:13,446 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-04-06 11:50:13,448 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-04-06 11:50:13,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:13,495 INFO L263 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 11:50:13,497 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:13,631 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-04-06 11:50:13,631 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:50:13,773 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-04-06 11:50:13,774 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:13,774 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [642323515] [2022-04-06 11:50:13,774 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:50:13,774 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2109650674] [2022-04-06 11:50:13,774 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2109650674] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:50:13,774 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:50:13,774 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-04-06 11:50:13,774 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1984658174] [2022-04-06 11:50:13,774 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:50:13,775 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 11:50:13,775 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:13,775 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 11:50:13,775 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-04-06 11:50:13,776 INFO L87 Difference]: Start difference. First operand 59 states and 71 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-04-06 11:50:13,959 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:13,959 INFO L93 Difference]: Finished difference Result 106 states and 146 transitions. [2022-04-06 11:50:13,959 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 11:50:13,960 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) Word has length 69 [2022-04-06 11:50:13,960 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:13,961 INFO L225 Difference]: With dead ends: 106 [2022-04-06 11:50:13,961 INFO L226 Difference]: Without dead ends: 98 [2022-04-06 11:50:13,961 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 129 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2022-04-06 11:50:13,962 INFO L913 BasicCegarLoop]: 60 mSDtfsCounter, 30 mSDsluCounter, 199 mSDsCounter, 0 mSdLazyCounter, 174 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 259 SdHoareTripleChecker+Invalid, 227 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 11:50:13,962 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 259 Invalid, 227 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 174 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 11:50:13,963 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2022-04-06 11:50:13,975 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 89. [2022-04-06 11:50:13,975 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 47 states have (on average 1.1914893617021276) internal successors, (56), 48 states have internal predecessors, (56), 34 states have call successors, (34), 8 states have call predecessors, (34), 7 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2022-04-06 11:50:13,976 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 122 transitions. [2022-04-06 11:50:13,977 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 122 transitions. Word has length 69 [2022-04-06 11:50:13,977 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:13,977 INFO L478 AbstractCegarLoop]: Abstraction has 89 states and 122 transitions. [2022-04-06 11:50:13,977 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-04-06 11:50:13,977 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 122 transitions. [2022-04-06 11:50:13,978 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-04-06 11:50:13,978 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:13,978 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:50:14,005 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-04-06 11:50:14,191 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:14,191 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:14,192 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:14,192 INFO L85 PathProgramCache]: Analyzing trace with hash -966489810, now seen corresponding path program 1 times [2022-04-06 11:50:14,192 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:14,192 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [324210152] [2022-04-06 11:50:14,192 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:14,192 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:14,203 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:14,204 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [719964530] [2022-04-06 11:50:14,204 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:14,204 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:14,204 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:14,205 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-04-06 11:50:14,206 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-04-06 11:50:14,257 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:14,259 INFO L263 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 18 conjunts are in the unsatisfiable core [2022-04-06 11:50:14,262 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:14,450 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 15 proven. 12 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-04-06 11:50:14,450 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:50:14,660 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-04-06 11:50:14,660 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:14,660 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [324210152] [2022-04-06 11:50:14,660 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:50:14,661 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [719964530] [2022-04-06 11:50:14,661 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [719964530] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:50:14,661 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:50:14,661 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-04-06 11:50:14,661 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1846783588] [2022-04-06 11:50:14,661 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:50:14,662 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-06 11:50:14,662 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:14,662 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-06 11:50:14,662 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2022-04-06 11:50:14,662 INFO L87 Difference]: Start difference. First operand 89 states and 122 transitions. Second operand has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) [2022-04-06 11:50:14,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:14,977 INFO L93 Difference]: Finished difference Result 132 states and 187 transitions. [2022-04-06 11:50:14,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-06 11:50:14,978 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) Word has length 75 [2022-04-06 11:50:14,979 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:14,981 INFO L225 Difference]: With dead ends: 132 [2022-04-06 11:50:14,981 INFO L226 Difference]: Without dead ends: 128 [2022-04-06 11:50:14,981 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 141 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=58, Invalid=214, Unknown=0, NotChecked=0, Total=272 [2022-04-06 11:50:14,982 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 26 mSDsluCounter, 257 mSDsCounter, 0 mSdLazyCounter, 409 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 303 SdHoareTripleChecker+Invalid, 440 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 409 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 11:50:14,982 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 303 Invalid, 440 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 409 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 11:50:14,983 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2022-04-06 11:50:14,999 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 96. [2022-04-06 11:50:14,999 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 51 states have (on average 1.1764705882352942) internal successors, (60), 53 states have internal predecessors, (60), 36 states have call successors, (36), 9 states have call predecessors, (36), 8 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2022-04-06 11:50:15,000 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 130 transitions. [2022-04-06 11:50:15,000 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 130 transitions. Word has length 75 [2022-04-06 11:50:15,001 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:15,001 INFO L478 AbstractCegarLoop]: Abstraction has 96 states and 130 transitions. [2022-04-06 11:50:15,001 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) [2022-04-06 11:50:15,001 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 130 transitions. [2022-04-06 11:50:15,002 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2022-04-06 11:50:15,002 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:15,002 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:50:15,029 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-04-06 11:50:15,226 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:15,227 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:15,227 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:15,227 INFO L85 PathProgramCache]: Analyzing trace with hash -271689658, now seen corresponding path program 2 times [2022-04-06 11:50:15,227 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:15,227 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [372566841] [2022-04-06 11:50:15,228 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:15,228 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:15,237 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:15,237 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [522822096] [2022-04-06 11:50:15,237 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 11:50:15,237 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:15,237 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:15,238 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-04-06 11:50:15,242 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-04-06 11:50:15,296 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 11:50:15,296 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 11:50:15,298 INFO L263 TraceCheckSpWp]: Trace formula consists of 213 conjuncts, 33 conjunts are in the unsatisfiable core [2022-04-06 11:50:15,300 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:15,782 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 15 proven. 18 refuted. 0 times theorem prover too weak. 105 trivial. 0 not checked. [2022-04-06 11:50:15,782 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:50:15,984 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2022-04-06 11:50:15,985 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:15,985 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [372566841] [2022-04-06 11:50:15,985 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:50:15,985 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [522822096] [2022-04-06 11:50:15,985 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [522822096] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:50:15,985 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:50:15,985 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 7] total 13 [2022-04-06 11:50:15,985 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1626495263] [2022-04-06 11:50:15,985 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:50:15,986 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-06 11:50:15,986 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:15,986 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-06 11:50:15,987 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2022-04-06 11:50:15,987 INFO L87 Difference]: Start difference. First operand 96 states and 130 transitions. Second operand has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2022-04-06 11:50:17,080 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:17,081 INFO L93 Difference]: Finished difference Result 128 states and 169 transitions. [2022-04-06 11:50:17,082 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-06 11:50:17,083 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 80 [2022-04-06 11:50:17,083 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:17,084 INFO L225 Difference]: With dead ends: 128 [2022-04-06 11:50:17,084 INFO L226 Difference]: Without dead ends: 126 [2022-04-06 11:50:17,085 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 167 GetRequests, 147 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 56 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=88, Invalid=332, Unknown=0, NotChecked=0, Total=420 [2022-04-06 11:50:17,085 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 40 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 349 mSolverCounterSat, 73 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 213 SdHoareTripleChecker+Invalid, 422 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 73 IncrementalHoareTripleChecker+Valid, 349 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2022-04-06 11:50:17,086 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [40 Valid, 213 Invalid, 422 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [73 Valid, 349 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2022-04-06 11:50:17,086 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2022-04-06 11:50:17,104 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 108. [2022-04-06 11:50:17,105 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 60 states have (on average 1.15) internal successors, (69), 62 states have internal predecessors, (69), 36 states have call successors, (36), 12 states have call predecessors, (36), 11 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2022-04-06 11:50:17,106 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 139 transitions. [2022-04-06 11:50:17,106 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 139 transitions. Word has length 80 [2022-04-06 11:50:17,106 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:17,106 INFO L478 AbstractCegarLoop]: Abstraction has 108 states and 139 transitions. [2022-04-06 11:50:17,106 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2022-04-06 11:50:17,107 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 139 transitions. [2022-04-06 11:50:17,107 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2022-04-06 11:50:17,107 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:17,107 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:50:17,132 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-04-06 11:50:17,332 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-04-06 11:50:17,333 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:17,333 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:17,333 INFO L85 PathProgramCache]: Analyzing trace with hash -1540307954, now seen corresponding path program 3 times [2022-04-06 11:50:17,333 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:17,333 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1059830740] [2022-04-06 11:50:17,333 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:17,333 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:17,343 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:17,344 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [669208034] [2022-04-06 11:50:17,344 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-06 11:50:17,344 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:17,344 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:17,348 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-04-06 11:50:17,350 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-04-06 11:50:17,397 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-04-06 11:50:17,398 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 11:50:17,399 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 36 conjunts are in the unsatisfiable core [2022-04-06 11:50:17,401 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:17,773 INFO L134 CoverageAnalysis]: Checked inductivity of 165 backedges. 31 proven. 8 refuted. 0 times theorem prover too weak. 126 trivial. 0 not checked. [2022-04-06 11:50:17,773 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:50:17,868 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:17,868 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1059830740] [2022-04-06 11:50:17,868 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:50:17,868 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [669208034] [2022-04-06 11:50:17,868 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [669208034] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 11:50:17,868 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 11:50:17,868 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-06 11:50:17,869 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2017000391] [2022-04-06 11:50:17,869 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-06 11:50:17,869 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 11:50:17,869 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:17,869 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 11:50:17,870 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-04-06 11:50:17,870 INFO L87 Difference]: Start difference. First operand 108 states and 139 transitions. Second operand has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2022-04-06 11:50:18,235 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:18,235 INFO L93 Difference]: Finished difference Result 144 states and 181 transitions. [2022-04-06 11:50:18,236 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 11:50:18,236 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 85 [2022-04-06 11:50:18,236 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:18,237 INFO L225 Difference]: With dead ends: 144 [2022-04-06 11:50:18,237 INFO L226 Difference]: Without dead ends: 142 [2022-04-06 11:50:18,238 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2022-04-06 11:50:18,238 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 20 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 244 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 258 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 244 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-06 11:50:18,239 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [25 Valid, 180 Invalid, 258 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 244 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-06 11:50:18,239 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2022-04-06 11:50:18,262 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 139. [2022-04-06 11:50:18,262 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 79 states have (on average 1.139240506329114) internal successors, (90), 81 states have internal predecessors, (90), 44 states have call successors, (44), 16 states have call predecessors, (44), 15 states have return successors, (42), 41 states have call predecessors, (42), 42 states have call successors, (42) [2022-04-06 11:50:18,263 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 176 transitions. [2022-04-06 11:50:18,263 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 176 transitions. Word has length 85 [2022-04-06 11:50:18,264 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:18,264 INFO L478 AbstractCegarLoop]: Abstraction has 139 states and 176 transitions. [2022-04-06 11:50:18,264 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2022-04-06 11:50:18,264 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 176 transitions. [2022-04-06 11:50:18,265 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-04-06 11:50:18,265 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:18,265 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:50:18,293 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-04-06 11:50:18,479 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-04-06 11:50:18,480 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:18,480 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:18,480 INFO L85 PathProgramCache]: Analyzing trace with hash -757951041, now seen corresponding path program 1 times [2022-04-06 11:50:18,480 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:18,480 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [64379075] [2022-04-06 11:50:18,480 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:18,481 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:18,494 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:18,495 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [741634767] [2022-04-06 11:50:18,495 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:18,495 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:18,495 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:18,501 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-04-06 11:50:18,502 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-04-06 11:50:18,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:18,566 INFO L263 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 37 conjunts are in the unsatisfiable core [2022-04-06 11:50:18,568 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:19,060 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2022-04-06 11:50:19,060 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:50:19,470 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2022-04-06 11:50:19,471 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:19,471 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [64379075] [2022-04-06 11:50:19,471 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:50:19,471 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [741634767] [2022-04-06 11:50:19,471 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [741634767] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:50:19,471 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:50:19,471 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2022-04-06 11:50:19,472 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2098149139] [2022-04-06 11:50:19,472 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:50:19,472 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-06 11:50:19,472 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:19,472 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-06 11:50:19,473 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2022-04-06 11:50:19,473 INFO L87 Difference]: Start difference. First operand 139 states and 176 transitions. Second operand has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2022-04-06 11:50:21,840 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:21,841 INFO L93 Difference]: Finished difference Result 228 states and 311 transitions. [2022-04-06 11:50:21,841 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-04-06 11:50:21,841 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) Word has length 91 [2022-04-06 11:50:21,841 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:21,843 INFO L225 Difference]: With dead ends: 228 [2022-04-06 11:50:21,843 INFO L226 Difference]: Without dead ends: 220 [2022-04-06 11:50:21,844 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 168 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=178, Invalid=692, Unknown=0, NotChecked=0, Total=870 [2022-04-06 11:50:21,844 INFO L913 BasicCegarLoop]: 78 mSDtfsCounter, 53 mSDsluCounter, 240 mSDsCounter, 0 mSdLazyCounter, 557 mSolverCounterSat, 133 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 318 SdHoareTripleChecker+Invalid, 690 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 133 IncrementalHoareTripleChecker+Valid, 557 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2022-04-06 11:50:21,844 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [57 Valid, 318 Invalid, 690 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [133 Valid, 557 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2022-04-06 11:50:21,845 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states. [2022-04-06 11:50:21,891 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 216. [2022-04-06 11:50:21,892 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 116 states have (on average 1.1810344827586208) internal successors, (137), 117 states have internal predecessors, (137), 81 states have call successors, (81), 19 states have call predecessors, (81), 18 states have return successors, (79), 79 states have call predecessors, (79), 79 states have call successors, (79) [2022-04-06 11:50:21,893 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 297 transitions. [2022-04-06 11:50:21,893 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 297 transitions. Word has length 91 [2022-04-06 11:50:21,894 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:21,894 INFO L478 AbstractCegarLoop]: Abstraction has 216 states and 297 transitions. [2022-04-06 11:50:21,894 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2022-04-06 11:50:21,894 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 297 transitions. [2022-04-06 11:50:21,895 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2022-04-06 11:50:21,895 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:21,895 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:50:21,921 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-04-06 11:50:22,111 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-04-06 11:50:22,111 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:22,112 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:22,112 INFO L85 PathProgramCache]: Analyzing trace with hash 1708635976, now seen corresponding path program 1 times [2022-04-06 11:50:22,112 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:22,112 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1288311378] [2022-04-06 11:50:22,112 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:22,112 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:22,122 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:22,122 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [326314143] [2022-04-06 11:50:22,122 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:22,122 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:22,122 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:22,126 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-04-06 11:50:22,145 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-04-06 11:50:22,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:50:22,194 INFO L263 TraceCheckSpWp]: Trace formula consists of 264 conjuncts, 52 conjunts are in the unsatisfiable core [2022-04-06 11:50:22,196 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:22,937 INFO L134 CoverageAnalysis]: Checked inductivity of 320 backedges. 79 proven. 33 refuted. 0 times theorem prover too weak. 208 trivial. 0 not checked. [2022-04-06 11:50:22,937 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:50:23,269 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 11:50:24,591 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:24,592 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1288311378] [2022-04-06 11:50:24,592 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:50:24,592 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [326314143] [2022-04-06 11:50:24,592 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [326314143] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 11:50:24,592 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 11:50:24,592 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-04-06 11:50:24,592 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1778474357] [2022-04-06 11:50:24,592 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-06 11:50:24,593 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-06 11:50:24,593 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:24,593 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-06 11:50:24,593 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=211, Unknown=0, NotChecked=0, Total=272 [2022-04-06 11:50:24,593 INFO L87 Difference]: Start difference. First operand 216 states and 297 transitions. Second operand has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 10 states have internal predecessors, (27), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) [2022-04-06 11:50:25,867 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.12s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:50:26,489 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:26,490 INFO L93 Difference]: Finished difference Result 226 states and 306 transitions. [2022-04-06 11:50:26,490 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-06 11:50:26,491 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 10 states have internal predecessors, (27), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) Word has length 107 [2022-04-06 11:50:26,491 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:26,492 INFO L225 Difference]: With dead ends: 226 [2022-04-06 11:50:26,492 INFO L226 Difference]: Without dead ends: 224 [2022-04-06 11:50:26,493 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 114 SyntacticMatches, 2 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=91, Invalid=329, Unknown=0, NotChecked=0, Total=420 [2022-04-06 11:50:26,493 INFO L913 BasicCegarLoop]: 48 mSDtfsCounter, 25 mSDsluCounter, 231 mSDsCounter, 0 mSdLazyCounter, 584 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 279 SdHoareTripleChecker+Invalid, 610 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 584 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2022-04-06 11:50:26,494 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 279 Invalid, 610 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 584 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2022-04-06 11:50:26,494 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 224 states. [2022-04-06 11:50:26,554 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 224 to 220. [2022-04-06 11:50:26,555 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 220 states, 119 states have (on average 1.1764705882352942) internal successors, (140), 120 states have internal predecessors, (140), 81 states have call successors, (81), 20 states have call predecessors, (81), 19 states have return successors, (79), 79 states have call predecessors, (79), 79 states have call successors, (79) [2022-04-06 11:50:26,558 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 220 states to 220 states and 300 transitions. [2022-04-06 11:50:26,558 INFO L78 Accepts]: Start accepts. Automaton has 220 states and 300 transitions. Word has length 107 [2022-04-06 11:50:26,558 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:26,558 INFO L478 AbstractCegarLoop]: Abstraction has 220 states and 300 transitions. [2022-04-06 11:50:26,558 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 10 states have internal predecessors, (27), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) [2022-04-06 11:50:26,559 INFO L276 IsEmpty]: Start isEmpty. Operand 220 states and 300 transitions. [2022-04-06 11:50:26,561 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2022-04-06 11:50:26,561 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:26,561 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 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, 1, 1, 1] [2022-04-06 11:50:26,580 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-04-06 11:50:26,767 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-04-06 11:50:26,768 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:26,768 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:26,768 INFO L85 PathProgramCache]: Analyzing trace with hash -426906627, now seen corresponding path program 4 times [2022-04-06 11:50:26,768 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:26,768 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1977696956] [2022-04-06 11:50:26,768 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:26,768 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:26,782 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:26,783 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1051476958] [2022-04-06 11:50:26,783 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 11:50:26,783 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:26,783 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:26,784 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-04-06 11:50:26,790 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-04-06 11:50:26,850 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 11:50:26,850 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 11:50:26,851 INFO L263 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-06 11:50:26,854 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:26,996 INFO L134 CoverageAnalysis]: Checked inductivity of 325 backedges. 135 proven. 0 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2022-04-06 11:50:26,996 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 11:50:26,996 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:26,996 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1977696956] [2022-04-06 11:50:26,996 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:50:26,996 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1051476958] [2022-04-06 11:50:26,997 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1051476958] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 11:50:26,997 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 11:50:26,997 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 11:50:26,997 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2016534771] [2022-04-06 11:50:26,997 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 11:50:26,997 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 11:50:26,997 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:26,998 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 11:50:26,998 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 11:50:26,998 INFO L87 Difference]: Start difference. First operand 220 states and 300 transitions. Second operand has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) [2022-04-06 11:50:27,106 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:27,106 INFO L93 Difference]: Finished difference Result 281 states and 378 transitions. [2022-04-06 11:50:27,107 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 11:50:27,107 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) Word has length 110 [2022-04-06 11:50:27,107 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:27,109 INFO L225 Difference]: With dead ends: 281 [2022-04-06 11:50:27,109 INFO L226 Difference]: Without dead ends: 201 [2022-04-06 11:50:27,114 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 106 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2022-04-06 11:50:27,116 INFO L913 BasicCegarLoop]: 56 mSDtfsCounter, 6 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 11:50:27,116 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 161 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 11:50:27,117 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 201 states. [2022-04-06 11:50:27,150 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 201 to 154. [2022-04-06 11:50:27,150 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 84 states have (on average 1.130952380952381) internal successors, (95), 85 states have internal predecessors, (95), 53 states have call successors, (53), 17 states have call predecessors, (53), 16 states have return successors, (51), 51 states have call predecessors, (51), 51 states have call successors, (51) [2022-04-06 11:50:27,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 199 transitions. [2022-04-06 11:50:27,153 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 199 transitions. Word has length 110 [2022-04-06 11:50:27,153 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:27,153 INFO L478 AbstractCegarLoop]: Abstraction has 154 states and 199 transitions. [2022-04-06 11:50:27,153 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) [2022-04-06 11:50:27,154 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 199 transitions. [2022-04-06 11:50:27,155 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2022-04-06 11:50:27,155 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:27,155 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:50:27,179 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2022-04-06 11:50:27,379 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-04-06 11:50:27,379 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:27,379 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:27,379 INFO L85 PathProgramCache]: Analyzing trace with hash -1431100670, now seen corresponding path program 2 times [2022-04-06 11:50:27,379 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:27,379 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [478754497] [2022-04-06 11:50:27,380 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:27,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:27,399 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:27,399 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [324778849] [2022-04-06 11:50:27,399 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 11:50:27,399 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:27,400 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:27,401 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 11:50:27,402 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-04-06 11:50:27,467 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 11:50:27,467 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 11:50:27,469 INFO L263 TraceCheckSpWp]: Trace formula consists of 306 conjuncts, 45 conjunts are in the unsatisfiable core [2022-04-06 11:50:27,471 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:28,286 INFO L134 CoverageAnalysis]: Checked inductivity of 545 backedges. 91 proven. 42 refuted. 0 times theorem prover too weak. 412 trivial. 0 not checked. [2022-04-06 11:50:28,286 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:50:28,971 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:50:28,971 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [478754497] [2022-04-06 11:50:28,971 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:50:28,971 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [324778849] [2022-04-06 11:50:28,971 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [324778849] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 11:50:28,971 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 11:50:28,971 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-06 11:50:28,971 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1745836949] [2022-04-06 11:50:28,971 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-06 11:50:28,971 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 11:50:28,975 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:50:28,975 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 11:50:28,975 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2022-04-06 11:50:28,976 INFO L87 Difference]: Start difference. First operand 154 states and 199 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 4 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2022-04-06 11:50:29,318 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:50:29,318 INFO L93 Difference]: Finished difference Result 195 states and 252 transitions. [2022-04-06 11:50:29,318 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 11:50:29,318 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 4 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) Word has length 129 [2022-04-06 11:50:29,319 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:50:29,320 INFO L225 Difference]: With dead ends: 195 [2022-04-06 11:50:29,320 INFO L226 Difference]: Without dead ends: 193 [2022-04-06 11:50:29,320 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 155 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=63, Invalid=209, Unknown=0, NotChecked=0, Total=272 [2022-04-06 11:50:29,321 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 17 mSDsluCounter, 132 mSDsCounter, 0 mSdLazyCounter, 236 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 172 SdHoareTripleChecker+Invalid, 249 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 236 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-06 11:50:29,321 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [18 Valid, 172 Invalid, 249 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 236 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-06 11:50:29,321 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 193 states. [2022-04-06 11:50:29,357 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 193 to 157. [2022-04-06 11:50:29,358 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 157 states, 87 states have (on average 1.1379310344827587) internal successors, (99), 88 states have internal predecessors, (99), 53 states have call successors, (53), 17 states have call predecessors, (53), 16 states have return successors, (51), 51 states have call predecessors, (51), 51 states have call successors, (51) [2022-04-06 11:50:29,359 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 203 transitions. [2022-04-06 11:50:29,359 INFO L78 Accepts]: Start accepts. Automaton has 157 states and 203 transitions. Word has length 129 [2022-04-06 11:50:29,360 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:50:29,360 INFO L478 AbstractCegarLoop]: Abstraction has 157 states and 203 transitions. [2022-04-06 11:50:29,360 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 4 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2022-04-06 11:50:29,360 INFO L276 IsEmpty]: Start isEmpty. Operand 157 states and 203 transitions. [2022-04-06 11:50:29,361 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 133 [2022-04-06 11:50:29,361 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:50:29,361 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:50:29,388 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-04-06 11:50:29,574 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-04-06 11:50:29,574 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:50:29,575 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:50:29,575 INFO L85 PathProgramCache]: Analyzing trace with hash -1491357193, now seen corresponding path program 3 times [2022-04-06 11:50:29,575 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:50:29,575 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1981354542] [2022-04-06 11:50:29,575 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:50:29,575 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:50:29,584 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:50:29,584 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2031723278] [2022-04-06 11:50:29,584 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-06 11:50:29,584 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:50:29,584 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:50:29,589 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 11:50:29,589 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-04-06 11:50:29,645 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-04-06 11:50:29,645 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 11:50:29,647 INFO L263 TraceCheckSpWp]: Trace formula consists of 210 conjuncts, 69 conjunts are in the unsatisfiable core [2022-04-06 11:50:29,649 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:50:30,649 INFO L134 CoverageAnalysis]: Checked inductivity of 550 backedges. 100 proven. 48 refuted. 0 times theorem prover too weak. 402 trivial. 0 not checked. [2022-04-06 11:50:30,650 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:51:09,333 INFO L134 CoverageAnalysis]: Checked inductivity of 550 backedges. 101 proven. 47 refuted. 0 times theorem prover too weak. 402 trivial. 0 not checked. [2022-04-06 11:51:09,333 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:51:09,333 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1981354542] [2022-04-06 11:51:09,333 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:51:09,334 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2031723278] [2022-04-06 11:51:09,334 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2031723278] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:51:09,334 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:51:09,334 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14] total 22 [2022-04-06 11:51:09,334 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2015400933] [2022-04-06 11:51:09,334 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:51:09,334 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-04-06 11:51:09,335 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:51:09,335 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-04-06 11:51:09,335 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=352, Unknown=4, NotChecked=0, Total=462 [2022-04-06 11:51:09,335 INFO L87 Difference]: Start difference. First operand 157 states and 203 transitions. Second operand has 22 states, 21 states have (on average 2.380952380952381) internal successors, (50), 20 states have internal predecessors, (50), 12 states have call successors, (42), 2 states have call predecessors, (42), 2 states have return successors, (39), 13 states have call predecessors, (39), 11 states have call successors, (39) [2022-04-06 11:51:11,361 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:51:13,550 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:51:16,018 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-04-06 11:51:21,960 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-04-06 11:51:24,072 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-04-06 11:51:27,495 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-04-06 11:51:30,314 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-04-06 11:51:37,331 WARN L232 SmtUtils]: Spent 6.57s on a formula simplification that was a NOOP. DAG size: 136 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:51:44,488 WARN L232 SmtUtils]: Spent 5.60s on a formula simplification that was a NOOP. DAG size: 128 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:51:49,394 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-04-06 11:51:51,710 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-04-06 11:51:54,678 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:52:00,754 WARN L232 SmtUtils]: Spent 5.91s on a formula simplification that was a NOOP. DAG size: 113 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:52:02,760 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-04-06 11:52:04,763 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-04-06 11:52:06,787 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-04-06 11:52:09,769 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-04-06 11:52:13,840 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-04-06 11:52:15,852 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-04-06 11:52:17,864 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-04-06 11:52:18,111 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:52:18,111 INFO L93 Difference]: Finished difference Result 242 states and 313 transitions. [2022-04-06 11:52:18,111 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-04-06 11:52:18,112 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 2.380952380952381) internal successors, (50), 20 states have internal predecessors, (50), 12 states have call successors, (42), 2 states have call predecessors, (42), 2 states have return successors, (39), 13 states have call predecessors, (39), 11 states have call successors, (39) Word has length 132 [2022-04-06 11:52:18,112 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:52:18,114 INFO L225 Difference]: With dead ends: 242 [2022-04-06 11:52:18,114 INFO L226 Difference]: Without dead ends: 238 [2022-04-06 11:52:18,115 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 276 GetRequests, 240 SyntacticMatches, 3 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 152 ImplicationChecksByTransitivity, 39.7s TimeCoverageRelationStatistics Valid=315, Invalid=870, Unknown=5, NotChecked=0, Total=1190 [2022-04-06 11:52:18,115 INFO L913 BasicCegarLoop]: 50 mSDtfsCounter, 78 mSDsluCounter, 301 mSDsCounter, 0 mSdLazyCounter, 847 mSolverCounterSat, 125 mSolverCounterUnsat, 17 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 44.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 90 SdHoareTripleChecker+Valid, 351 SdHoareTripleChecker+Invalid, 989 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 125 IncrementalHoareTripleChecker+Valid, 847 IncrementalHoareTripleChecker+Invalid, 17 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 44.1s IncrementalHoareTripleChecker+Time [2022-04-06 11:52:18,116 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [90 Valid, 351 Invalid, 989 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [125 Valid, 847 Invalid, 17 Unknown, 0 Unchecked, 44.1s Time] [2022-04-06 11:52:18,116 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 238 states. [2022-04-06 11:52:18,166 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 238 to 196. [2022-04-06 11:52:18,166 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 196 states, 110 states have (on average 1.1181818181818182) internal successors, (123), 110 states have internal predecessors, (123), 65 states have call successors, (65), 22 states have call predecessors, (65), 20 states have return successors, (63), 63 states have call predecessors, (63), 63 states have call successors, (63) [2022-04-06 11:52:18,167 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 196 states to 196 states and 251 transitions. [2022-04-06 11:52:18,167 INFO L78 Accepts]: Start accepts. Automaton has 196 states and 251 transitions. Word has length 132 [2022-04-06 11:52:18,168 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:52:18,168 INFO L478 AbstractCegarLoop]: Abstraction has 196 states and 251 transitions. [2022-04-06 11:52:18,168 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 2.380952380952381) internal successors, (50), 20 states have internal predecessors, (50), 12 states have call successors, (42), 2 states have call predecessors, (42), 2 states have return successors, (39), 13 states have call predecessors, (39), 11 states have call successors, (39) [2022-04-06 11:52:18,168 INFO L276 IsEmpty]: Start isEmpty. Operand 196 states and 251 transitions. [2022-04-06 11:52:18,169 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2022-04-06 11:52:18,169 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:52:18,170 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:52:18,194 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-04-06 11:52:18,387 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:52:18,387 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:52:18,388 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:52:18,388 INFO L85 PathProgramCache]: Analyzing trace with hash -928796440, now seen corresponding path program 2 times [2022-04-06 11:52:18,388 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:52:18,388 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1073885188] [2022-04-06 11:52:18,388 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:52:18,388 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:52:18,395 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:52:18,395 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [701245875] [2022-04-06 11:52:18,395 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 11:52:18,395 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:52:18,395 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:52:18,396 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 11:52:18,399 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-04-06 11:52:18,468 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 11:52:18,468 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 11:52:18,470 INFO L263 TraceCheckSpWp]: Trace formula consists of 333 conjuncts, 67 conjunts are in the unsatisfiable core [2022-04-06 11:52:18,472 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:52:20,187 INFO L134 CoverageAnalysis]: Checked inductivity of 615 backedges. 69 proven. 90 refuted. 0 times theorem prover too weak. 456 trivial. 0 not checked. [2022-04-06 11:52:20,188 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:52:20,911 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 11:52:20,915 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 11:52:33,542 INFO L134 CoverageAnalysis]: Checked inductivity of 615 backedges. 69 proven. 90 refuted. 0 times theorem prover too weak. 456 trivial. 0 not checked. [2022-04-06 11:52:33,542 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:52:33,542 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1073885188] [2022-04-06 11:52:33,542 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:52:33,542 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [701245875] [2022-04-06 11:52:33,542 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [701245875] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:52:33,542 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:52:33,542 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 29 [2022-04-06 11:52:33,543 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1936643865] [2022-04-06 11:52:33,543 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:52:33,543 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2022-04-06 11:52:33,543 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:52:33,544 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2022-04-06 11:52:33,544 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=135, Invalid=674, Unknown=3, NotChecked=0, Total=812 [2022-04-06 11:52:33,544 INFO L87 Difference]: Start difference. First operand 196 states and 251 transitions. Second operand has 29 states, 27 states have (on average 1.9259259259259258) internal successors, (52), 26 states have internal predecessors, (52), 16 states have call successors, (44), 2 states have call predecessors, (44), 2 states have return successors, (41), 12 states have call predecessors, (41), 14 states have call successors, (41) [2022-04-06 11:52:46,914 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-04-06 11:52:51,451 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-04-06 11:52:53,596 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-04-06 11:53:03,900 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-04-06 11:53:22,348 WARN L232 SmtUtils]: Spent 16.66s on a formula simplification. DAG size of input: 117 DAG size of output: 115 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:53:36,879 WARN L232 SmtUtils]: Spent 11.49s on a formula simplification. DAG size of input: 103 DAG size of output: 101 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:53:39,788 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-04-06 11:54:05,354 WARN L232 SmtUtils]: Spent 15.11s on a formula simplification that was a NOOP. DAG size: 74 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:54:08,109 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-04-06 11:54:10,112 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-04-06 11:54:12,114 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-04-06 11:54:14,117 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-04-06 11:54:15,616 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.50s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:54:17,622 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-04-06 11:54:43,569 WARN L232 SmtUtils]: Spent 21.86s on a formula simplification. DAG size of input: 121 DAG size of output: 119 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:55:22,625 WARN L232 SmtUtils]: Spent 31.13s on a formula simplification. DAG size of input: 100 DAG size of output: 98 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:55:33,359 WARN L232 SmtUtils]: Spent 6.89s on a formula simplification. DAG size of input: 96 DAG size of output: 94 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:55:53,998 WARN L232 SmtUtils]: Spent 8.67s on a formula simplification. DAG size of input: 102 DAG size of output: 100 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:56:06,114 WARN L232 SmtUtils]: Spent 8.24s on a formula simplification. DAG size of input: 101 DAG size of output: 99 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:56:14,828 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:56:14,828 INFO L93 Difference]: Finished difference Result 296 states and 399 transitions. [2022-04-06 11:56:14,829 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2022-04-06 11:56:14,829 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 27 states have (on average 1.9259259259259258) internal successors, (52), 26 states have internal predecessors, (52), 16 states have call successors, (44), 2 states have call predecessors, (44), 2 states have return successors, (41), 12 states have call predecessors, (41), 14 states have call successors, (41) Word has length 138 [2022-04-06 11:56:14,829 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:56:14,831 INFO L225 Difference]: With dead ends: 296 [2022-04-06 11:56:14,831 INFO L226 Difference]: Without dead ends: 290 [2022-04-06 11:56:14,833 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 313 GetRequests, 246 SyntacticMatches, 2 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1175 ImplicationChecksByTransitivity, 178.8s TimeCoverageRelationStatistics Valid=886, Invalid=3522, Unknown=14, NotChecked=0, Total=4422 [2022-04-06 11:56:14,834 INFO L913 BasicCegarLoop]: 60 mSDtfsCounter, 141 mSDsluCounter, 416 mSDsCounter, 0 mSdLazyCounter, 1626 mSolverCounterSat, 372 mSolverCounterUnsat, 10 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 53.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 146 SdHoareTripleChecker+Valid, 476 SdHoareTripleChecker+Invalid, 2008 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 372 IncrementalHoareTripleChecker+Valid, 1626 IncrementalHoareTripleChecker+Invalid, 10 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 53.7s IncrementalHoareTripleChecker+Time [2022-04-06 11:56:14,834 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [146 Valid, 476 Invalid, 2008 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [372 Valid, 1626 Invalid, 10 Unknown, 0 Unchecked, 53.7s Time] [2022-04-06 11:56:14,836 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 290 states. [2022-04-06 11:56:14,930 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 290 to 225. [2022-04-06 11:56:14,931 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 225 states, 125 states have (on average 1.104) internal successors, (138), 125 states have internal predecessors, (138), 77 states have call successors, (77), 24 states have call predecessors, (77), 22 states have return successors, (75), 75 states have call predecessors, (75), 75 states have call successors, (75) [2022-04-06 11:56:14,932 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 225 states to 225 states and 290 transitions. [2022-04-06 11:56:14,932 INFO L78 Accepts]: Start accepts. Automaton has 225 states and 290 transitions. Word has length 138 [2022-04-06 11:56:14,933 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:56:14,933 INFO L478 AbstractCegarLoop]: Abstraction has 225 states and 290 transitions. [2022-04-06 11:56:14,933 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 27 states have (on average 1.9259259259259258) internal successors, (52), 26 states have internal predecessors, (52), 16 states have call successors, (44), 2 states have call predecessors, (44), 2 states have return successors, (41), 12 states have call predecessors, (41), 14 states have call successors, (41) [2022-04-06 11:56:14,933 INFO L276 IsEmpty]: Start isEmpty. Operand 225 states and 290 transitions. [2022-04-06 11:56:14,934 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 183 [2022-04-06 11:56:14,934 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:56:14,934 INFO L499 BasicCegarLoop]: trace histogram [25, 24, 24, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:56:14,960 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-04-06 11:56:15,151 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-04-06 11:56:15,151 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:56:15,152 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:56:15,152 INFO L85 PathProgramCache]: Analyzing trace with hash 980979816, now seen corresponding path program 3 times [2022-04-06 11:56:15,152 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:56:15,152 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [759254803] [2022-04-06 11:56:15,152 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:56:15,152 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:56:15,160 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:56:15,161 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1341050958] [2022-04-06 11:56:15,161 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-06 11:56:15,161 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:56:15,161 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:56:15,162 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 11:56:15,168 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-04-06 11:56:15,420 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-04-06 11:56:15,420 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 11:56:15,422 INFO L263 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 70 conjunts are in the unsatisfiable core [2022-04-06 11:56:15,425 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:56:16,933 INFO L134 CoverageAnalysis]: Checked inductivity of 1309 backedges. 175 proven. 99 refuted. 0 times theorem prover too weak. 1035 trivial. 0 not checked. [2022-04-06 11:56:16,933 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:56:18,248 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 11:56:45,506 WARN L232 SmtUtils]: Spent 8.29s on a formula simplification that was a NOOP. DAG size: 52 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:57:20,021 INFO L134 CoverageAnalysis]: Checked inductivity of 1309 backedges. 169 proven. 90 refuted. 0 times theorem prover too weak. 1050 trivial. 0 not checked. [2022-04-06 11:57:20,021 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:57:20,021 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [759254803] [2022-04-06 11:57:20,021 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:57:20,021 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1341050958] [2022-04-06 11:57:20,021 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1341050958] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:57:20,022 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:57:20,022 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 17] total 31 [2022-04-06 11:57:20,022 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [770792952] [2022-04-06 11:57:20,022 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:57:20,022 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2022-04-06 11:57:20,022 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:57:20,022 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2022-04-06 11:57:20,023 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=158, Invalid=768, Unknown=4, NotChecked=0, Total=930 [2022-04-06 11:57:20,023 INFO L87 Difference]: Start difference. First operand 225 states and 290 transitions. Second operand has 31 states, 28 states have (on average 2.0714285714285716) internal successors, (58), 27 states have internal predecessors, (58), 17 states have call successors, (47), 2 states have call predecessors, (47), 3 states have return successors, (45), 13 states have call predecessors, (45), 15 states have call successors, (45) [2022-04-06 11:57:23,160 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.24s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:57:25,189 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-04-06 11:57:29,250 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-04-06 11:57:31,269 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-04-06 11:57:39,352 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-04-06 11:57:41,996 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-04-06 11:57:43,999 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-04-06 11:57:45,272 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.25s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:58:12,676 WARN L232 SmtUtils]: Spent 24.93s on a formula simplification that was a NOOP. DAG size: 117 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:58:24,591 WARN L232 SmtUtils]: Spent 10.08s on a formula simplification that was a NOOP. DAG size: 113 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:58:26,650 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-04-06 11:58:30,504 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-04-06 11:58:35,480 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.98s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:58:38,001 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-04-06 11:58:57,003 WARN L232 SmtUtils]: Spent 16.27s on a formula simplification that was a NOOP. DAG size: 61 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:59:03,249 WARN L232 SmtUtils]: Spent 6.09s on a formula simplification that was a NOOP. DAG size: 110 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:59:06,483 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-04-06 11:59:09,746 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-04-06 11:59:11,754 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:59:12,922 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.05s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:59:16,452 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-04-06 11:59:18,669 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse3 (* c_main_~q~0 c_main_~x~0)) (.cse4 (* c_main_~s~0 c_main_~y~0))) (let ((.cse0 (not (= c_main_~b~0 (+ .cse3 .cse4))))) (and (or (not (= c_main_~c~0 0)) (not (= (+ (* c_main_~b~0 c_main_~k~0) c_main_~c~0) c_main_~a~0)) (= (+ (* (+ c_main_~r~0 (* (- 1) (* c_main_~s~0 c_main_~k~0))) c_main_~y~0) (* (+ c_main_~p~0 (* (- 1) c_main_~q~0 c_main_~k~0)) c_main_~x~0)) 0) (<= c_main_~b~0 c_main_~c~0) .cse0) (let ((.cse2 (+ (* (- 1) c_main_~b~0) c_main_~a~0))) (let ((.cse1 (div .cse2 c_main_~b~0))) (or (= c_main_~b~0 0) (<= (+ (* c_main_~b~0 2) (* .cse1 c_main_~b~0)) c_main_~a~0) (not (= (mod .cse2 c_main_~b~0) 0)) .cse0 (= (+ (* .cse1 c_main_~q~0 c_main_~x~0) .cse3 .cse4 (* .cse1 c_main_~s~0 c_main_~y~0)) (+ (* c_main_~p~0 c_main_~x~0) (* c_main_~r~0 c_main_~y~0))))))))) is different from true [2022-04-06 11:59:21,543 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-04-06 11:59:26,211 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-04-06 11:59:35,311 WARN L232 SmtUtils]: Spent 7.68s on a formula simplification that was a NOOP. DAG size: 138 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:59:37,729 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.49s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 12:00:13,420 WARN L232 SmtUtils]: Spent 18.67s on a formula simplification that was a NOOP. DAG size: 91 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 12:00:15,505 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-04-06 12:00:17,325 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.16s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 12:00:21,877 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-04-06 12:00:26,494 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.03s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 12:00:37,736 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.71s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 12:00:39,738 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-04-06 12:00:41,782 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-04-06 12:01:04,635 WARN L232 SmtUtils]: Spent 6.39s on a formula simplification. DAG size of input: 113 DAG size of output: 93 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 12:01:11,299 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:01:11,299 INFO L93 Difference]: Finished difference Result 354 states and 473 transitions. [2022-04-06 12:01:11,299 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2022-04-06 12:01:11,299 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 28 states have (on average 2.0714285714285716) internal successors, (58), 27 states have internal predecessors, (58), 17 states have call successors, (47), 2 states have call predecessors, (47), 3 states have return successors, (45), 13 states have call predecessors, (45), 15 states have call successors, (45) Word has length 182 [2022-04-06 12:01:11,300 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:01:11,300 INFO L225 Difference]: With dead ends: 354 [2022-04-06 12:01:11,300 INFO L226 Difference]: Without dead ends: 0 [2022-04-06 12:01:11,302 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 400 GetRequests, 333 SyntacticMatches, 3 SemanticMatches, 64 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 1016 ImplicationChecksByTransitivity, 183.7s TimeCoverageRelationStatistics Valid=813, Invalid=3342, Unknown=9, NotChecked=126, Total=4290 [2022-04-06 12:01:11,302 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 90 mSDsluCounter, 267 mSDsCounter, 0 mSdLazyCounter, 1299 mSolverCounterSat, 233 mSolverCounterUnsat, 19 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 72.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 93 SdHoareTripleChecker+Valid, 311 SdHoareTripleChecker+Invalid, 1566 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 233 IncrementalHoareTripleChecker+Valid, 1299 IncrementalHoareTripleChecker+Invalid, 19 IncrementalHoareTripleChecker+Unknown, 15 IncrementalHoareTripleChecker+Unchecked, 72.2s IncrementalHoareTripleChecker+Time [2022-04-06 12:01:11,302 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [93 Valid, 311 Invalid, 1566 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [233 Valid, 1299 Invalid, 19 Unknown, 15 Unchecked, 72.2s Time] [2022-04-06 12:01:11,303 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-06 12:01:11,303 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-06 12:01:11,303 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-06 12:01:11,303 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-06 12:01:11,303 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 182 [2022-04-06 12:01:11,303 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:01:11,303 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-06 12:01:11,304 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 28 states have (on average 2.0714285714285716) internal successors, (58), 27 states have internal predecessors, (58), 17 states have call successors, (47), 2 states have call predecessors, (47), 3 states have return successors, (45), 13 states have call predecessors, (45), 15 states have call successors, (45) [2022-04-06 12:01:11,304 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-06 12:01:11,304 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-06 12:01:11,306 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-06 12:01:11,334 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2022-04-06 12:01:11,519 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-04-06 12:01:11,521 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions.