/usr/bin/java -ea -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/AutomizerC.xml -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf -i ../../../trunk/examples/svcomp/nla-digbench/ps6-ll.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-fb4f59a-m [2022-04-27 11:57:51,814 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-27 11:57:51,816 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-27 11:57:51,838 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-27 11:57:51,839 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-27 11:57:51,839 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-27 11:57:51,840 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-27 11:57:51,842 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-27 11:57:51,843 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-27 11:57:51,844 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-27 11:57:51,844 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-27 11:57:51,845 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-27 11:57:51,846 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-27 11:57:51,846 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-27 11:57:51,847 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-27 11:57:51,848 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-27 11:57:51,849 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-27 11:57:51,850 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-27 11:57:51,851 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-27 11:57:51,853 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-27 11:57:51,854 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-27 11:57:51,855 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-27 11:57:51,856 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-27 11:57:51,857 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-27 11:57:51,858 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-27 11:57:51,860 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-27 11:57:51,860 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-27 11:57:51,861 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-27 11:57:51,861 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-27 11:57:51,862 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-27 11:57:51,862 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-27 11:57:51,863 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-27 11:57:51,863 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-27 11:57:51,864 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-27 11:57:51,865 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-27 11:57:51,865 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-27 11:57:51,866 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-27 11:57:51,866 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-27 11:57:51,866 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-27 11:57:51,866 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-27 11:57:51,867 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-27 11:57:51,868 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-27 11:57:51,868 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf [2022-04-27 11:57:51,884 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-27 11:57:51,885 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-27 11:57:51,885 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-04-27 11:57:51,885 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-04-27 11:57:51,886 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-27 11:57:51,886 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-27 11:57:51,886 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-27 11:57:51,887 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-27 11:57:51,887 INFO L138 SettingsManager]: * Use SBE=true [2022-04-27 11:57:51,891 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-27 11:57:51,891 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-27 11:57:51,891 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-27 11:57:51,892 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-27 11:57:51,892 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-27 11:57:51,892 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-27 11:57:51,892 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-27 11:57:51,892 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-27 11:57:51,892 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-27 11:57:51,893 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-27 11:57:51,893 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-27 11:57:51,893 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-27 11:57:51,894 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-27 11:57:51,894 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-27 11:57:51,894 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-27 11:57:51,894 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-27 11:57:51,895 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-27 11:57:51,895 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-27 11:57:51,895 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-27 11:57:51,896 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-27 11:57:51,896 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-27 11:57:51,896 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-04-27 11:57:51,896 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-04-27 11:57:51,896 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-27 11:57:51,896 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode 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-27 11:57:52,099 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-27 11:57:52,118 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-27 11:57:52,120 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-27 11:57:52,121 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-27 11:57:52,121 INFO L275 PluginConnector]: CDTParser initialized [2022-04-27 11:57:52,122 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench/ps6-ll.c [2022-04-27 11:57:52,178 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/347cf5c83/eeaa28199d0d44b1b8aa15f04ccd0114/FLAG7f17a1e82 [2022-04-27 11:57:52,513 INFO L306 CDTParser]: Found 1 translation units. [2022-04-27 11:57:52,514 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench/ps6-ll.c [2022-04-27 11:57:52,518 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/347cf5c83/eeaa28199d0d44b1b8aa15f04ccd0114/FLAG7f17a1e82 [2022-04-27 11:57:52,946 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/347cf5c83/eeaa28199d0d44b1b8aa15f04ccd0114 [2022-04-27 11:57:52,948 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-27 11:57:52,949 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-27 11:57:52,953 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-27 11:57:52,953 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-27 11:57:52,957 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-27 11:57:52,958 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.04 11:57:52" (1/1) ... [2022-04-27 11:57:52,959 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@13196ee9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 11:57:52, skipping insertion in model container [2022-04-27 11:57:52,959 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.04 11:57:52" (1/1) ... [2022-04-27 11:57:52,968 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-27 11:57:52,997 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-27 11:57:53,122 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/ps6-ll.c[458,471] [2022-04-27 11:57:53,153 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-27 11:57:53,159 INFO L203 MainTranslator]: Completed pre-run [2022-04-27 11:57:53,170 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/ps6-ll.c[458,471] [2022-04-27 11:57:53,178 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-27 11:57:53,191 INFO L208 MainTranslator]: Completed translation [2022-04-27 11:57:53,191 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 11:57:53 WrapperNode [2022-04-27 11:57:53,191 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-27 11:57:53,192 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-27 11:57:53,192 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-27 11:57:53,192 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-27 11:57:53,204 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 11:57:53" (1/1) ... [2022-04-27 11:57:53,204 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 11:57:53" (1/1) ... [2022-04-27 11:57:53,211 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 11:57:53" (1/1) ... [2022-04-27 11:57:53,211 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 11:57:53" (1/1) ... [2022-04-27 11:57:53,224 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 11:57:53" (1/1) ... [2022-04-27 11:57:53,227 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 11:57:53" (1/1) ... [2022-04-27 11:57:53,227 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 11:57:53" (1/1) ... [2022-04-27 11:57:53,229 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-27 11:57:53,229 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-27 11:57:53,230 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-27 11:57:53,230 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-27 11:57:53,230 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 11:57:53" (1/1) ... [2022-04-27 11:57:53,245 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-27 11:57:53,252 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-27 11:57:53,261 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-27 11:57:53,269 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-27 11:57:53,290 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-27 11:57:53,290 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-27 11:57:53,290 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-27 11:57:53,290 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-27 11:57:53,290 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-27 11:57:53,290 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-27 11:57:53,290 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-27 11:57:53,291 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-27 11:57:53,291 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-27 11:57:53,291 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-27 11:57:53,291 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_short [2022-04-27 11:57:53,291 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-27 11:57:53,291 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-27 11:57:53,291 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-27 11:57:53,291 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-27 11:57:53,292 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-27 11:57:53,292 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-27 11:57:53,292 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-27 11:57:53,292 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-27 11:57:53,292 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-27 11:57:53,346 INFO L234 CfgBuilder]: Building ICFG [2022-04-27 11:57:53,347 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-27 11:57:53,465 INFO L275 CfgBuilder]: Performing block encoding [2022-04-27 11:57:53,471 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-27 11:57:53,471 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-27 11:57:53,474 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.04 11:57:53 BoogieIcfgContainer [2022-04-27 11:57:53,474 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-27 11:57:53,489 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-27 11:57:53,490 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-27 11:57:53,493 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-27 11:57:53,493 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 27.04 11:57:52" (1/3) ... [2022-04-27 11:57:53,494 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2870feb2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.04 11:57:53, skipping insertion in model container [2022-04-27 11:57:53,494 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 11:57:53" (2/3) ... [2022-04-27 11:57:53,494 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2870feb2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.04 11:57:53, skipping insertion in model container [2022-04-27 11:57:53,494 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.04 11:57:53" (3/3) ... [2022-04-27 11:57:53,495 INFO L111 eAbstractionObserver]: Analyzing ICFG ps6-ll.c [2022-04-27 11:57:53,516 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-27 11:57:53,516 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-27 11:57:53,556 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-27 11:57:53,562 INFO L357 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=PETRI_NET, 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, mPorIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@6ba846dc, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@237cea87 [2022-04-27 11:57:53,562 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-27 11:57:53,569 INFO L276 IsEmpty]: Start isEmpty. Operand has 28 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-27 11:57:53,575 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-27 11:57:53,576 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 11:57:53,576 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 11:57:53,577 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 11:57:53,583 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 11:57:53,583 INFO L85 PathProgramCache]: Analyzing trace with hash -630235283, now seen corresponding path program 1 times [2022-04-27 11:57:53,590 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 11:57:53,590 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [353209906] [2022-04-27 11:57:53,591 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 11:57:53,592 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 11:57:53,661 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 11:57:53,705 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-27 11:57:53,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 11:57:53,723 INFO L290 TraceCheckUtils]: 0: Hoare triple {40#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(9, 2);call #Ultimate.allocInit(12, 3); {31#true} is VALID [2022-04-27 11:57:53,724 INFO L290 TraceCheckUtils]: 1: Hoare triple {31#true} assume true; {31#true} is VALID [2022-04-27 11:57:53,724 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {31#true} {31#true} #60#return; {31#true} is VALID [2022-04-27 11:57:53,725 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-27 11:57:53,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 11:57:53,745 INFO L290 TraceCheckUtils]: 0: Hoare triple {31#true} ~cond := #in~cond; {31#true} is VALID [2022-04-27 11:57:53,747 INFO L290 TraceCheckUtils]: 1: Hoare triple {31#true} assume 0 == ~cond;assume false; {32#false} is VALID [2022-04-27 11:57:53,747 INFO L290 TraceCheckUtils]: 2: Hoare triple {32#false} assume true; {32#false} is VALID [2022-04-27 11:57:53,747 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {32#false} {31#true} #52#return; {32#false} is VALID [2022-04-27 11:57:53,753 INFO L272 TraceCheckUtils]: 0: Hoare triple {31#true} call ULTIMATE.init(); {40#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-27 11:57:53,753 INFO L290 TraceCheckUtils]: 1: Hoare triple {40#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(9, 2);call #Ultimate.allocInit(12, 3); {31#true} is VALID [2022-04-27 11:57:53,753 INFO L290 TraceCheckUtils]: 2: Hoare triple {31#true} assume true; {31#true} is VALID [2022-04-27 11:57:53,753 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {31#true} {31#true} #60#return; {31#true} is VALID [2022-04-27 11:57:53,754 INFO L272 TraceCheckUtils]: 4: Hoare triple {31#true} call #t~ret5 := main(); {31#true} is VALID [2022-04-27 11:57:53,754 INFO L290 TraceCheckUtils]: 5: Hoare triple {31#true} havoc ~k~0;havoc ~y~0;havoc ~x~0;havoc ~c~0;assume -32768 <= #t~nondet4 && #t~nondet4 <= 32767;~k~0 := #t~nondet4;havoc #t~nondet4; {31#true} is VALID [2022-04-27 11:57:53,754 INFO L272 TraceCheckUtils]: 6: Hoare triple {31#true} call assume_abort_if_not((if ~k~0 <= 256 then 1 else 0)); {31#true} is VALID [2022-04-27 11:57:53,754 INFO L290 TraceCheckUtils]: 7: Hoare triple {31#true} ~cond := #in~cond; {31#true} is VALID [2022-04-27 11:57:53,758 INFO L290 TraceCheckUtils]: 8: Hoare triple {31#true} assume 0 == ~cond;assume false; {32#false} is VALID [2022-04-27 11:57:53,758 INFO L290 TraceCheckUtils]: 9: Hoare triple {32#false} assume true; {32#false} is VALID [2022-04-27 11:57:53,758 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {32#false} {31#true} #52#return; {32#false} is VALID [2022-04-27 11:57:53,758 INFO L290 TraceCheckUtils]: 11: Hoare triple {32#false} ~y~0 := 0;~x~0 := 0;~c~0 := 0; {32#false} is VALID [2022-04-27 11:57:53,759 INFO L290 TraceCheckUtils]: 12: Hoare triple {32#false} assume false; {32#false} is VALID [2022-04-27 11:57:53,759 INFO L272 TraceCheckUtils]: 13: Hoare triple {32#false} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {32#false} is VALID [2022-04-27 11:57:53,759 INFO L290 TraceCheckUtils]: 14: Hoare triple {32#false} ~cond := #in~cond; {32#false} is VALID [2022-04-27 11:57:53,759 INFO L290 TraceCheckUtils]: 15: Hoare triple {32#false} assume 0 == ~cond; {32#false} is VALID [2022-04-27 11:57:53,760 INFO L290 TraceCheckUtils]: 16: Hoare triple {32#false} assume !false; {32#false} is VALID [2022-04-27 11:57:53,760 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-27 11:57:53,761 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-27 11:57:53,761 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [353209906] [2022-04-27 11:57:53,761 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [353209906] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-27 11:57:53,762 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-27 11:57:53,762 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-27 11:57:53,763 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1650336001] [2022-04-27 11:57:53,764 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-27 11:57:53,768 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-27 11:57:53,769 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-27 11:57:53,780 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-27 11:57:53,820 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 17 edges. 17 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:57:53,820 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-27 11:57:53,821 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-27 11:57:53,838 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-27 11:57:53,838 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-27 11:57:53,840 INFO L87 Difference]: Start difference. First operand has 28 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-27 11:57:54,264 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:54,265 INFO L93 Difference]: Finished difference Result 47 states and 61 transitions. [2022-04-27 11:57:54,265 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-27 11:57:54,265 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-27 11:57:54,265 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-27 11:57:54,266 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-27 11:57:54,282 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 61 transitions. [2022-04-27 11:57:54,283 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-27 11:57:54,294 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 61 transitions. [2022-04-27 11:57:54,294 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 61 transitions. [2022-04-27 11:57:54,377 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 61 edges. 61 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:57:54,384 INFO L225 Difference]: With dead ends: 47 [2022-04-27 11:57:54,384 INFO L226 Difference]: Without dead ends: 23 [2022-04-27 11:57:54,386 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 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-27 11:57:54,391 INFO L413 NwaCegarLoop]: 26 mSDtfsCounter, 15 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 6 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 6 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-27 11:57:54,391 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 29 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 6 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-27 11:57:54,402 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2022-04-27 11:57:54,412 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2022-04-27 11:57:54,412 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-27 11:57:54,413 INFO L82 GeneralOperation]: Start isEquivalent. First operand 23 states. Second operand has 23 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-27 11:57:54,414 INFO L74 IsIncluded]: Start isIncluded. First operand 23 states. Second operand has 23 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-27 11:57:54,414 INFO L87 Difference]: Start difference. First operand 23 states. Second operand has 23 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-27 11:57:54,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:54,418 INFO L93 Difference]: Finished difference Result 23 states and 25 transitions. [2022-04-27 11:57:54,419 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 25 transitions. [2022-04-27 11:57:54,419 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:57:54,419 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:57:54,420 INFO L74 IsIncluded]: Start isIncluded. First operand has 23 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand 23 states. [2022-04-27 11:57:54,420 INFO L87 Difference]: Start difference. First operand has 23 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand 23 states. [2022-04-27 11:57:54,423 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:54,423 INFO L93 Difference]: Finished difference Result 23 states and 25 transitions. [2022-04-27 11:57:54,423 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 25 transitions. [2022-04-27 11:57:54,423 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:57:54,424 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:57:54,424 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-27 11:57:54,424 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-27 11:57:54,424 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-27 11:57:54,426 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 25 transitions. [2022-04-27 11:57:54,427 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 25 transitions. Word has length 17 [2022-04-27 11:57:54,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-27 11:57:54,428 INFO L495 AbstractCegarLoop]: Abstraction has 23 states and 25 transitions. [2022-04-27 11:57:54,428 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-27 11:57:54,428 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 25 transitions. [2022-04-27 11:57:54,429 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-27 11:57:54,429 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 11:57:54,429 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 11:57:54,429 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-27 11:57:54,430 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 11:57:54,430 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 11:57:54,431 INFO L85 PathProgramCache]: Analyzing trace with hash 51610547, now seen corresponding path program 1 times [2022-04-27 11:57:54,431 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 11:57:54,431 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [173787136] [2022-04-27 11:57:54,431 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 11:57:54,431 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 11:57:54,450 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-27 11:57:54,450 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1790560950] [2022-04-27 11:57:54,451 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 11:57:54,451 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-27 11:57:54,451 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-27 11:57:54,452 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-27 11:57:54,463 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-27 11:57:54,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 11:57:54,506 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-27 11:57:54,515 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 11:57:54,518 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-27 11:57:54,681 INFO L272 TraceCheckUtils]: 0: Hoare triple {186#true} call ULTIMATE.init(); {186#true} is VALID [2022-04-27 11:57:54,682 INFO L290 TraceCheckUtils]: 1: Hoare triple {186#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(9, 2);call #Ultimate.allocInit(12, 3); {186#true} is VALID [2022-04-27 11:57:54,682 INFO L290 TraceCheckUtils]: 2: Hoare triple {186#true} assume true; {186#true} is VALID [2022-04-27 11:57:54,682 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {186#true} {186#true} #60#return; {186#true} is VALID [2022-04-27 11:57:54,683 INFO L272 TraceCheckUtils]: 4: Hoare triple {186#true} call #t~ret5 := main(); {186#true} is VALID [2022-04-27 11:57:54,683 INFO L290 TraceCheckUtils]: 5: Hoare triple {186#true} havoc ~k~0;havoc ~y~0;havoc ~x~0;havoc ~c~0;assume -32768 <= #t~nondet4 && #t~nondet4 <= 32767;~k~0 := #t~nondet4;havoc #t~nondet4; {186#true} is VALID [2022-04-27 11:57:54,683 INFO L272 TraceCheckUtils]: 6: Hoare triple {186#true} call assume_abort_if_not((if ~k~0 <= 256 then 1 else 0)); {186#true} is VALID [2022-04-27 11:57:54,683 INFO L290 TraceCheckUtils]: 7: Hoare triple {186#true} ~cond := #in~cond; {186#true} is VALID [2022-04-27 11:57:54,685 INFO L290 TraceCheckUtils]: 8: Hoare triple {186#true} assume !(0 == ~cond); {186#true} is VALID [2022-04-27 11:57:54,685 INFO L290 TraceCheckUtils]: 9: Hoare triple {186#true} assume true; {186#true} is VALID [2022-04-27 11:57:54,685 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {186#true} {186#true} #52#return; {186#true} is VALID [2022-04-27 11:57:54,686 INFO L290 TraceCheckUtils]: 11: Hoare triple {186#true} ~y~0 := 0;~x~0 := 0;~c~0 := 0; {224#(and (= main_~x~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:54,687 INFO L290 TraceCheckUtils]: 12: Hoare triple {224#(and (= main_~x~0 0) (= main_~y~0 0))} assume !false; {224#(and (= main_~x~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:54,688 INFO L272 TraceCheckUtils]: 13: Hoare triple {224#(and (= main_~x~0 0) (= main_~y~0 0))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {231#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-27 11:57:54,689 INFO L290 TraceCheckUtils]: 14: Hoare triple {231#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {235#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-27 11:57:54,690 INFO L290 TraceCheckUtils]: 15: Hoare triple {235#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {187#false} is VALID [2022-04-27 11:57:54,690 INFO L290 TraceCheckUtils]: 16: Hoare triple {187#false} assume !false; {187#false} is VALID [2022-04-27 11:57:54,690 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-27 11:57:54,690 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-27 11:57:54,691 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-27 11:57:54,691 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [173787136] [2022-04-27 11:57:54,691 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-27 11:57:54,693 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1790560950] [2022-04-27 11:57:54,696 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1790560950] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-27 11:57:54,696 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-27 11:57:54,696 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-27 11:57:54,697 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2060473760] [2022-04-27 11:57:54,697 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-27 11:57:54,699 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-27 11:57:54,699 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-27 11:57:54,700 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-27 11:57:54,719 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 17 edges. 17 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:57:54,720 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-27 11:57:54,721 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-27 11:57:54,722 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-27 11:57:54,722 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-27 11:57:54,723 INFO L87 Difference]: Start difference. First operand 23 states and 25 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-27 11:57:54,866 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:54,866 INFO L93 Difference]: Finished difference Result 34 states and 38 transitions. [2022-04-27 11:57:54,866 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-27 11:57:54,867 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-27 11:57:54,867 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-27 11:57:54,868 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-27 11:57:54,877 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 38 transitions. [2022-04-27 11:57:54,877 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-27 11:57:54,881 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 38 transitions. [2022-04-27 11:57:54,881 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 38 transitions. [2022-04-27 11:57:54,920 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 38 edges. 38 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:57:54,922 INFO L225 Difference]: With dead ends: 34 [2022-04-27 11:57:54,923 INFO L226 Difference]: Without dead ends: 30 [2022-04-27 11:57:54,923 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-27 11:57:54,925 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 6 mSDsluCounter, 55 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-27 11:57:54,926 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 77 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-27 11:57:54,928 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2022-04-27 11:57:54,936 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2022-04-27 11:57:54,936 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-27 11:57:54,937 INFO L82 GeneralOperation]: Start isEquivalent. First operand 30 states. Second operand has 30 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 19 states have internal predecessors, (20), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-27 11:57:54,938 INFO L74 IsIncluded]: Start isIncluded. First operand 30 states. Second operand has 30 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 19 states have internal predecessors, (20), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-27 11:57:54,938 INFO L87 Difference]: Start difference. First operand 30 states. Second operand has 30 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 19 states have internal predecessors, (20), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-27 11:57:54,943 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:54,943 INFO L93 Difference]: Finished difference Result 30 states and 32 transitions. [2022-04-27 11:57:54,943 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 32 transitions. [2022-04-27 11:57:54,951 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:57:54,951 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:57:54,951 INFO L74 IsIncluded]: Start isIncluded. First operand has 30 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 19 states have internal predecessors, (20), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand 30 states. [2022-04-27 11:57:54,952 INFO L87 Difference]: Start difference. First operand has 30 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 19 states have internal predecessors, (20), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand 30 states. [2022-04-27 11:57:54,956 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:54,956 INFO L93 Difference]: Finished difference Result 30 states and 32 transitions. [2022-04-27 11:57:54,956 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 32 transitions. [2022-04-27 11:57:54,957 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:57:54,957 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:57:54,958 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-27 11:57:54,958 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-27 11:57:54,960 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 19 states have internal predecessors, (20), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-27 11:57:54,969 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 32 transitions. [2022-04-27 11:57:54,970 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 32 transitions. Word has length 17 [2022-04-27 11:57:54,970 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-27 11:57:54,970 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 32 transitions. [2022-04-27 11:57:54,971 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-27 11:57:54,971 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 32 transitions. [2022-04-27 11:57:54,972 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-27 11:57:54,973 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 11:57:54,973 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 11:57:55,002 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-27 11:57:55,187 WARN L477 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-27 11:57:55,188 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 11:57:55,189 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 11:57:55,189 INFO L85 PathProgramCache]: Analyzing trace with hash 311787922, now seen corresponding path program 1 times [2022-04-27 11:57:55,189 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 11:57:55,189 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1105405126] [2022-04-27 11:57:55,190 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 11:57:55,190 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 11:57:55,211 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-27 11:57:55,211 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1559455093] [2022-04-27 11:57:55,211 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 11:57:55,212 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-27 11:57:55,212 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-27 11:57:55,219 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-27 11:57:55,220 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-27 11:57:55,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 11:57:55,272 INFO L263 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-27 11:57:55,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 11:57:55,284 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-27 11:57:55,467 INFO L272 TraceCheckUtils]: 0: Hoare triple {397#true} call ULTIMATE.init(); {397#true} is VALID [2022-04-27 11:57:55,467 INFO L290 TraceCheckUtils]: 1: Hoare triple {397#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(9, 2);call #Ultimate.allocInit(12, 3); {397#true} is VALID [2022-04-27 11:57:55,467 INFO L290 TraceCheckUtils]: 2: Hoare triple {397#true} assume true; {397#true} is VALID [2022-04-27 11:57:55,468 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {397#true} {397#true} #60#return; {397#true} is VALID [2022-04-27 11:57:55,468 INFO L272 TraceCheckUtils]: 4: Hoare triple {397#true} call #t~ret5 := main(); {397#true} is VALID [2022-04-27 11:57:55,468 INFO L290 TraceCheckUtils]: 5: Hoare triple {397#true} havoc ~k~0;havoc ~y~0;havoc ~x~0;havoc ~c~0;assume -32768 <= #t~nondet4 && #t~nondet4 <= 32767;~k~0 := #t~nondet4;havoc #t~nondet4; {397#true} is VALID [2022-04-27 11:57:55,468 INFO L272 TraceCheckUtils]: 6: Hoare triple {397#true} call assume_abort_if_not((if ~k~0 <= 256 then 1 else 0)); {397#true} is VALID [2022-04-27 11:57:55,472 INFO L290 TraceCheckUtils]: 7: Hoare triple {397#true} ~cond := #in~cond; {397#true} is VALID [2022-04-27 11:57:55,472 INFO L290 TraceCheckUtils]: 8: Hoare triple {397#true} assume !(0 == ~cond); {397#true} is VALID [2022-04-27 11:57:55,472 INFO L290 TraceCheckUtils]: 9: Hoare triple {397#true} assume true; {397#true} is VALID [2022-04-27 11:57:55,473 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {397#true} {397#true} #52#return; {397#true} is VALID [2022-04-27 11:57:55,473 INFO L290 TraceCheckUtils]: 11: Hoare triple {397#true} ~y~0 := 0;~x~0 := 0;~c~0 := 0; {435#(and (= main_~x~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:55,474 INFO L290 TraceCheckUtils]: 12: Hoare triple {435#(and (= main_~x~0 0) (= main_~y~0 0))} assume !false; {435#(and (= main_~x~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:55,474 INFO L272 TraceCheckUtils]: 13: Hoare triple {435#(and (= main_~x~0 0) (= main_~y~0 0))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {397#true} is VALID [2022-04-27 11:57:55,476 INFO L290 TraceCheckUtils]: 14: Hoare triple {397#true} ~cond := #in~cond; {397#true} is VALID [2022-04-27 11:57:55,476 INFO L290 TraceCheckUtils]: 15: Hoare triple {397#true} assume !(0 == ~cond); {397#true} is VALID [2022-04-27 11:57:55,477 INFO L290 TraceCheckUtils]: 16: Hoare triple {397#true} assume true; {397#true} is VALID [2022-04-27 11:57:55,477 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {397#true} {435#(and (= main_~x~0 0) (= main_~y~0 0))} #54#return; {435#(and (= main_~x~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:55,478 INFO L290 TraceCheckUtils]: 18: Hoare triple {435#(and (= main_~x~0 0) (= main_~y~0 0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~y~0 := 1 + ~y~0;~x~0 := ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~x~0; {457#(and (= (+ (- 1) main_~y~0) 0) (= main_~x~0 (* main_~y~0 (* (* main_~y~0 (* main_~y~0 main_~y~0)) main_~y~0))))} is VALID [2022-04-27 11:57:55,479 INFO L290 TraceCheckUtils]: 19: Hoare triple {457#(and (= (+ (- 1) main_~y~0) 0) (= main_~x~0 (* main_~y~0 (* (* main_~y~0 (* main_~y~0 main_~y~0)) main_~y~0))))} assume !false; {457#(and (= (+ (- 1) main_~y~0) 0) (= main_~x~0 (* main_~y~0 (* (* main_~y~0 (* main_~y~0 main_~y~0)) main_~y~0))))} is VALID [2022-04-27 11:57:55,481 INFO L272 TraceCheckUtils]: 20: Hoare triple {457#(and (= (+ (- 1) main_~y~0) 0) (= main_~x~0 (* main_~y~0 (* (* main_~y~0 (* main_~y~0 main_~y~0)) main_~y~0))))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {464#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-27 11:57:55,481 INFO L290 TraceCheckUtils]: 21: Hoare triple {464#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {468#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-27 11:57:55,482 INFO L290 TraceCheckUtils]: 22: Hoare triple {468#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {398#false} is VALID [2022-04-27 11:57:55,482 INFO L290 TraceCheckUtils]: 23: Hoare triple {398#false} assume !false; {398#false} is VALID [2022-04-27 11:57:55,483 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-27 11:57:55,483 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-27 11:57:55,680 INFO L290 TraceCheckUtils]: 23: Hoare triple {398#false} assume !false; {398#false} is VALID [2022-04-27 11:57:55,681 INFO L290 TraceCheckUtils]: 22: Hoare triple {468#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {398#false} is VALID [2022-04-27 11:57:55,681 INFO L290 TraceCheckUtils]: 21: Hoare triple {464#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {468#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-27 11:57:55,682 INFO L272 TraceCheckUtils]: 20: Hoare triple {484#(= (+ (* 2 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 6 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 5 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0))) (+ (* main_~x~0 12) (* main_~y~0 main_~y~0)))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {464#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-27 11:57:55,683 INFO L290 TraceCheckUtils]: 19: Hoare triple {484#(= (+ (* 2 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 6 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 5 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0))) (+ (* main_~x~0 12) (* main_~y~0 main_~y~0)))} assume !false; {484#(= (+ (* 2 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 6 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 5 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0))) (+ (* main_~x~0 12) (* main_~y~0 main_~y~0)))} is VALID [2022-04-27 11:57:55,740 INFO L290 TraceCheckUtils]: 18: Hoare triple {484#(= (+ (* 2 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 6 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 5 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0))) (+ (* main_~x~0 12) (* main_~y~0 main_~y~0)))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~y~0 := 1 + ~y~0;~x~0 := ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~x~0; {484#(= (+ (* 2 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 6 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 5 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0))) (+ (* main_~x~0 12) (* main_~y~0 main_~y~0)))} is VALID [2022-04-27 11:57:55,740 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {397#true} {484#(= (+ (* 2 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 6 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 5 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0))) (+ (* main_~x~0 12) (* main_~y~0 main_~y~0)))} #54#return; {484#(= (+ (* 2 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 6 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 5 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0))) (+ (* main_~x~0 12) (* main_~y~0 main_~y~0)))} is VALID [2022-04-27 11:57:55,740 INFO L290 TraceCheckUtils]: 16: Hoare triple {397#true} assume true; {397#true} is VALID [2022-04-27 11:57:55,741 INFO L290 TraceCheckUtils]: 15: Hoare triple {397#true} assume !(0 == ~cond); {397#true} is VALID [2022-04-27 11:57:55,741 INFO L290 TraceCheckUtils]: 14: Hoare triple {397#true} ~cond := #in~cond; {397#true} is VALID [2022-04-27 11:57:55,741 INFO L272 TraceCheckUtils]: 13: Hoare triple {484#(= (+ (* 2 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 6 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 5 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0))) (+ (* main_~x~0 12) (* main_~y~0 main_~y~0)))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {397#true} is VALID [2022-04-27 11:57:55,741 INFO L290 TraceCheckUtils]: 12: Hoare triple {484#(= (+ (* 2 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 6 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 5 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0))) (+ (* main_~x~0 12) (* main_~y~0 main_~y~0)))} assume !false; {484#(= (+ (* 2 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 6 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 5 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0))) (+ (* main_~x~0 12) (* main_~y~0 main_~y~0)))} is VALID [2022-04-27 11:57:55,742 INFO L290 TraceCheckUtils]: 11: Hoare triple {397#true} ~y~0 := 0;~x~0 := 0;~c~0 := 0; {484#(= (+ (* 2 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 6 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0 main_~y~0)) (* 5 (* main_~y~0 main_~y~0 main_~y~0 main_~y~0))) (+ (* main_~x~0 12) (* main_~y~0 main_~y~0)))} is VALID [2022-04-27 11:57:55,742 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {397#true} {397#true} #52#return; {397#true} is VALID [2022-04-27 11:57:55,742 INFO L290 TraceCheckUtils]: 9: Hoare triple {397#true} assume true; {397#true} is VALID [2022-04-27 11:57:55,742 INFO L290 TraceCheckUtils]: 8: Hoare triple {397#true} assume !(0 == ~cond); {397#true} is VALID [2022-04-27 11:57:55,742 INFO L290 TraceCheckUtils]: 7: Hoare triple {397#true} ~cond := #in~cond; {397#true} is VALID [2022-04-27 11:57:55,743 INFO L272 TraceCheckUtils]: 6: Hoare triple {397#true} call assume_abort_if_not((if ~k~0 <= 256 then 1 else 0)); {397#true} is VALID [2022-04-27 11:57:55,743 INFO L290 TraceCheckUtils]: 5: Hoare triple {397#true} havoc ~k~0;havoc ~y~0;havoc ~x~0;havoc ~c~0;assume -32768 <= #t~nondet4 && #t~nondet4 <= 32767;~k~0 := #t~nondet4;havoc #t~nondet4; {397#true} is VALID [2022-04-27 11:57:55,743 INFO L272 TraceCheckUtils]: 4: Hoare triple {397#true} call #t~ret5 := main(); {397#true} is VALID [2022-04-27 11:57:55,743 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {397#true} {397#true} #60#return; {397#true} is VALID [2022-04-27 11:57:55,743 INFO L290 TraceCheckUtils]: 2: Hoare triple {397#true} assume true; {397#true} is VALID [2022-04-27 11:57:55,743 INFO L290 TraceCheckUtils]: 1: Hoare triple {397#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(9, 2);call #Ultimate.allocInit(12, 3); {397#true} is VALID [2022-04-27 11:57:55,744 INFO L272 TraceCheckUtils]: 0: Hoare triple {397#true} call ULTIMATE.init(); {397#true} is VALID [2022-04-27 11:57:55,744 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-04-27 11:57:55,744 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-27 11:57:55,744 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1105405126] [2022-04-27 11:57:55,744 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-27 11:57:55,745 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1559455093] [2022-04-27 11:57:55,745 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1559455093] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-27 11:57:55,745 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-27 11:57:55,745 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-27 11:57:55,745 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [998348410] [2022-04-27 11:57:55,745 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-27 11:57:55,746 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2022-04-27 11:57:55,746 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-27 11:57:55,746 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-27 11:57:55,817 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 23 edges. 23 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:57:55,817 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-27 11:57:55,817 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-27 11:57:55,818 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-27 11:57:55,818 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-27 11:57:55,818 INFO L87 Difference]: Start difference. First operand 30 states and 32 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-27 11:57:55,935 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:55,935 INFO L93 Difference]: Finished difference Result 36 states and 37 transitions. [2022-04-27 11:57:55,935 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-27 11:57:55,936 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2022-04-27 11:57:55,936 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-27 11:57:55,936 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-27 11:57:55,937 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 30 transitions. [2022-04-27 11:57:55,937 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-27 11:57:55,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 30 transitions. [2022-04-27 11:57:55,938 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 30 transitions. [2022-04-27 11:57:56,015 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 30 edges. 30 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:57:56,016 INFO L225 Difference]: With dead ends: 36 [2022-04-27 11:57:56,016 INFO L226 Difference]: Without dead ends: 32 [2022-04-27 11:57:56,017 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 40 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-27 11:57:56,018 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 6 mSDsluCounter, 47 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-27 11:57:56,018 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 67 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-27 11:57:56,019 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-27 11:57:56,024 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-04-27 11:57:56,025 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-27 11:57:56,025 INFO L82 GeneralOperation]: Start isEquivalent. First operand 32 states. Second operand has 32 states, 20 states have (on average 1.05) internal successors, (21), 20 states have internal predecessors, (21), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-27 11:57:56,025 INFO L74 IsIncluded]: Start isIncluded. First operand 32 states. Second operand has 32 states, 20 states have (on average 1.05) internal successors, (21), 20 states have internal predecessors, (21), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-27 11:57:56,025 INFO L87 Difference]: Start difference. First operand 32 states. Second operand has 32 states, 20 states have (on average 1.05) internal successors, (21), 20 states have internal predecessors, (21), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-27 11:57:56,027 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:56,028 INFO L93 Difference]: Finished difference Result 32 states and 33 transitions. [2022-04-27 11:57:56,028 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 33 transitions. [2022-04-27 11:57:56,028 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:57:56,028 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:57:56,028 INFO L74 IsIncluded]: Start isIncluded. First operand has 32 states, 20 states have (on average 1.05) internal successors, (21), 20 states have internal predecessors, (21), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand 32 states. [2022-04-27 11:57:56,029 INFO L87 Difference]: Start difference. First operand has 32 states, 20 states have (on average 1.05) internal successors, (21), 20 states have internal predecessors, (21), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand 32 states. [2022-04-27 11:57:56,030 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:56,030 INFO L93 Difference]: Finished difference Result 32 states and 33 transitions. [2022-04-27 11:57:56,030 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 33 transitions. [2022-04-27 11:57:56,031 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:57:56,031 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:57:56,031 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-27 11:57:56,031 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-27 11:57:56,031 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 20 states have (on average 1.05) internal successors, (21), 20 states have internal predecessors, (21), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-27 11:57:56,033 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 33 transitions. [2022-04-27 11:57:56,033 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 33 transitions. Word has length 24 [2022-04-27 11:57:56,033 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-27 11:57:56,033 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 33 transitions. [2022-04-27 11:57:56,033 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-27 11:57:56,033 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 33 transitions. [2022-04-27 11:57:56,034 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2022-04-27 11:57:56,034 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 11:57:56,034 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 11:57:56,055 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-27 11:57:56,247 WARN L477 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-27 11:57:56,247 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 11:57:56,248 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 11:57:56,248 INFO L85 PathProgramCache]: Analyzing trace with hash 1106328449, now seen corresponding path program 1 times [2022-04-27 11:57:56,248 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 11:57:56,249 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1902477869] [2022-04-27 11:57:56,249 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 11:57:56,249 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 11:57:56,263 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-27 11:57:56,263 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [72606614] [2022-04-27 11:57:56,263 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 11:57:56,263 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-27 11:57:56,264 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-27 11:57:56,264 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-27 11:57:56,298 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-27 11:57:56,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 11:57:56,319 INFO L263 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-27 11:57:56,330 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 11:57:56,331 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-27 11:57:56,634 INFO L272 TraceCheckUtils]: 0: Hoare triple {711#true} call ULTIMATE.init(); {711#true} is VALID [2022-04-27 11:57:56,635 INFO L290 TraceCheckUtils]: 1: Hoare triple {711#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(9, 2);call #Ultimate.allocInit(12, 3); {711#true} is VALID [2022-04-27 11:57:56,635 INFO L290 TraceCheckUtils]: 2: Hoare triple {711#true} assume true; {711#true} is VALID [2022-04-27 11:57:56,635 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {711#true} {711#true} #60#return; {711#true} is VALID [2022-04-27 11:57:56,635 INFO L272 TraceCheckUtils]: 4: Hoare triple {711#true} call #t~ret5 := main(); {711#true} is VALID [2022-04-27 11:57:56,635 INFO L290 TraceCheckUtils]: 5: Hoare triple {711#true} havoc ~k~0;havoc ~y~0;havoc ~x~0;havoc ~c~0;assume -32768 <= #t~nondet4 && #t~nondet4 <= 32767;~k~0 := #t~nondet4;havoc #t~nondet4; {711#true} is VALID [2022-04-27 11:57:56,636 INFO L272 TraceCheckUtils]: 6: Hoare triple {711#true} call assume_abort_if_not((if ~k~0 <= 256 then 1 else 0)); {711#true} is VALID [2022-04-27 11:57:56,636 INFO L290 TraceCheckUtils]: 7: Hoare triple {711#true} ~cond := #in~cond; {711#true} is VALID [2022-04-27 11:57:56,636 INFO L290 TraceCheckUtils]: 8: Hoare triple {711#true} assume !(0 == ~cond); {711#true} is VALID [2022-04-27 11:57:56,636 INFO L290 TraceCheckUtils]: 9: Hoare triple {711#true} assume true; {711#true} is VALID [2022-04-27 11:57:56,636 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {711#true} {711#true} #52#return; {711#true} is VALID [2022-04-27 11:57:56,637 INFO L290 TraceCheckUtils]: 11: Hoare triple {711#true} ~y~0 := 0;~x~0 := 0;~c~0 := 0; {749#(and (= main_~c~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:56,637 INFO L290 TraceCheckUtils]: 12: Hoare triple {749#(and (= main_~c~0 0) (= main_~y~0 0))} assume !false; {749#(and (= main_~c~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:56,637 INFO L272 TraceCheckUtils]: 13: Hoare triple {749#(and (= main_~c~0 0) (= main_~y~0 0))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {711#true} is VALID [2022-04-27 11:57:56,637 INFO L290 TraceCheckUtils]: 14: Hoare triple {711#true} ~cond := #in~cond; {711#true} is VALID [2022-04-27 11:57:56,638 INFO L290 TraceCheckUtils]: 15: Hoare triple {711#true} assume !(0 == ~cond); {711#true} is VALID [2022-04-27 11:57:56,638 INFO L290 TraceCheckUtils]: 16: Hoare triple {711#true} assume true; {711#true} is VALID [2022-04-27 11:57:56,640 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {711#true} {749#(and (= main_~c~0 0) (= main_~y~0 0))} #54#return; {749#(and (= main_~c~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:56,641 INFO L290 TraceCheckUtils]: 18: Hoare triple {749#(and (= main_~c~0 0) (= main_~y~0 0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~y~0 := 1 + ~y~0;~x~0 := ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~x~0; {771#(and (= (+ (- 1) main_~y~0) 0) (< 0 main_~k~0) (<= main_~c~0 1))} is VALID [2022-04-27 11:57:56,641 INFO L290 TraceCheckUtils]: 19: Hoare triple {771#(and (= (+ (- 1) main_~y~0) 0) (< 0 main_~k~0) (<= main_~c~0 1))} assume !false; {771#(and (= (+ (- 1) main_~y~0) 0) (< 0 main_~k~0) (<= main_~c~0 1))} is VALID [2022-04-27 11:57:56,641 INFO L272 TraceCheckUtils]: 20: Hoare triple {771#(and (= (+ (- 1) main_~y~0) 0) (< 0 main_~k~0) (<= main_~c~0 1))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {711#true} is VALID [2022-04-27 11:57:56,641 INFO L290 TraceCheckUtils]: 21: Hoare triple {711#true} ~cond := #in~cond; {711#true} is VALID [2022-04-27 11:57:56,642 INFO L290 TraceCheckUtils]: 22: Hoare triple {711#true} assume !(0 == ~cond); {711#true} is VALID [2022-04-27 11:57:56,642 INFO L290 TraceCheckUtils]: 23: Hoare triple {711#true} assume true; {711#true} is VALID [2022-04-27 11:57:56,642 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {711#true} {771#(and (= (+ (- 1) main_~y~0) 0) (< 0 main_~k~0) (<= main_~c~0 1))} #54#return; {771#(and (= (+ (- 1) main_~y~0) 0) (< 0 main_~k~0) (<= main_~c~0 1))} is VALID [2022-04-27 11:57:56,643 INFO L290 TraceCheckUtils]: 25: Hoare triple {771#(and (= (+ (- 1) main_~y~0) 0) (< 0 main_~k~0) (<= main_~c~0 1))} assume !(~c~0 < ~k~0); {793#(and (= (+ (- 1) main_~y~0) 0) (<= main_~k~0 1) (< 0 main_~k~0))} is VALID [2022-04-27 11:57:56,643 INFO L272 TraceCheckUtils]: 26: Hoare triple {793#(and (= (+ (- 1) main_~y~0) 0) (<= main_~k~0 1) (< 0 main_~k~0))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {711#true} is VALID [2022-04-27 11:57:56,643 INFO L290 TraceCheckUtils]: 27: Hoare triple {711#true} ~cond := #in~cond; {711#true} is VALID [2022-04-27 11:57:56,643 INFO L290 TraceCheckUtils]: 28: Hoare triple {711#true} assume !(0 == ~cond); {711#true} is VALID [2022-04-27 11:57:56,644 INFO L290 TraceCheckUtils]: 29: Hoare triple {711#true} assume true; {711#true} is VALID [2022-04-27 11:57:56,645 INFO L284 TraceCheckUtils]: 30: Hoare quadruple {711#true} {793#(and (= (+ (- 1) main_~y~0) 0) (<= main_~k~0 1) (< 0 main_~k~0))} #56#return; {793#(and (= (+ (- 1) main_~y~0) 0) (<= main_~k~0 1) (< 0 main_~k~0))} is VALID [2022-04-27 11:57:56,656 INFO L272 TraceCheckUtils]: 31: Hoare triple {793#(and (= (+ (- 1) main_~y~0) 0) (<= main_~k~0 1) (< 0 main_~k~0))} call __VERIFIER_assert((if ~k~0 * ~y~0 == ~y~0 * ~y~0 then 1 else 0)); {812#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-27 11:57:56,656 INFO L290 TraceCheckUtils]: 32: Hoare triple {812#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {816#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-27 11:57:56,657 INFO L290 TraceCheckUtils]: 33: Hoare triple {816#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {712#false} is VALID [2022-04-27 11:57:56,657 INFO L290 TraceCheckUtils]: 34: Hoare triple {712#false} assume !false; {712#false} is VALID [2022-04-27 11:57:56,657 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-27 11:57:56,657 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-27 11:57:56,990 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-27 11:57:56,990 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1902477869] [2022-04-27 11:57:56,990 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-27 11:57:56,991 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [72606614] [2022-04-27 11:57:56,991 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [72606614] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-27 11:57:56,991 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-27 11:57:56,991 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-04-27 11:57:56,991 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1728327833] [2022-04-27 11:57:56,991 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-27 11:57:56,992 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 35 [2022-04-27 11:57:56,992 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-27 11:57:56,992 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-04-27 11:57:57,021 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 29 edges. 29 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:57:57,021 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-27 11:57:57,021 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-27 11:57:57,022 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-27 11:57:57,022 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-04-27 11:57:57,022 INFO L87 Difference]: Start difference. First operand 32 states and 33 transitions. Second operand has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-04-27 11:57:57,282 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:57,282 INFO L93 Difference]: Finished difference Result 41 states and 44 transitions. [2022-04-27 11:57:57,282 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-27 11:57:57,282 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 35 [2022-04-27 11:57:57,282 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-27 11:57:57,283 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-04-27 11:57:57,287 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 40 transitions. [2022-04-27 11:57:57,288 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-04-27 11:57:57,291 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 40 transitions. [2022-04-27 11:57:57,291 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 7 states and 40 transitions. [2022-04-27 11:57:57,324 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 40 edges. 40 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:57:57,328 INFO L225 Difference]: With dead ends: 41 [2022-04-27 11:57:57,328 INFO L226 Difference]: Without dead ends: 35 [2022-04-27 11:57:57,329 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 43 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2022-04-27 11:57:57,332 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 2 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-27 11:57:57,333 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 125 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-27 11:57:57,335 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-04-27 11:57:57,348 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2022-04-27 11:57:57,348 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-27 11:57:57,348 INFO L82 GeneralOperation]: Start isEquivalent. First operand 35 states. Second operand has 35 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 22 states have internal predecessors, (23), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-27 11:57:57,348 INFO L74 IsIncluded]: Start isIncluded. First operand 35 states. Second operand has 35 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 22 states have internal predecessors, (23), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-27 11:57:57,349 INFO L87 Difference]: Start difference. First operand 35 states. Second operand has 35 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 22 states have internal predecessors, (23), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-27 11:57:57,350 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:57,350 INFO L93 Difference]: Finished difference Result 35 states and 37 transitions. [2022-04-27 11:57:57,350 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 37 transitions. [2022-04-27 11:57:57,351 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:57:57,351 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:57:57,351 INFO L74 IsIncluded]: Start isIncluded. First operand has 35 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 22 states have internal predecessors, (23), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand 35 states. [2022-04-27 11:57:57,351 INFO L87 Difference]: Start difference. First operand has 35 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 22 states have internal predecessors, (23), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand 35 states. [2022-04-27 11:57:57,354 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:57,354 INFO L93 Difference]: Finished difference Result 35 states and 37 transitions. [2022-04-27 11:57:57,354 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 37 transitions. [2022-04-27 11:57:57,357 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:57:57,357 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:57:57,357 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-27 11:57:57,357 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-27 11:57:57,358 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 22 states have internal predecessors, (23), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-27 11:57:57,360 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 37 transitions. [2022-04-27 11:57:57,360 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 37 transitions. Word has length 35 [2022-04-27 11:57:57,361 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-27 11:57:57,361 INFO L495 AbstractCegarLoop]: Abstraction has 35 states and 37 transitions. [2022-04-27 11:57:57,362 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-04-27 11:57:57,362 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 37 transitions. [2022-04-27 11:57:57,363 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-04-27 11:57:57,363 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 11:57:57,363 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 11:57:57,384 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-27 11:57:57,579 WARN L477 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-27 11:57:57,580 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 11:57:57,580 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 11:57:57,580 INFO L85 PathProgramCache]: Analyzing trace with hash 1564024736, now seen corresponding path program 2 times [2022-04-27 11:57:57,580 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 11:57:57,580 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1666547257] [2022-04-27 11:57:57,580 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 11:57:57,581 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 11:57:57,606 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-27 11:57:57,606 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [633764505] [2022-04-27 11:57:57,606 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-27 11:57:57,606 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-27 11:57:57,607 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-27 11:57:57,624 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-27 11:57:57,675 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-27 11:57:57,753 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-27 11:57:57,753 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-27 11:57:57,754 INFO L263 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 16 conjunts are in the unsatisfiable core [2022-04-27 11:57:57,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 11:57:57,766 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-27 11:57:58,076 INFO L272 TraceCheckUtils]: 0: Hoare triple {1066#true} call ULTIMATE.init(); {1066#true} is VALID [2022-04-27 11:57:58,077 INFO L290 TraceCheckUtils]: 1: Hoare triple {1066#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(9, 2);call #Ultimate.allocInit(12, 3); {1066#true} is VALID [2022-04-27 11:57:58,077 INFO L290 TraceCheckUtils]: 2: Hoare triple {1066#true} assume true; {1066#true} is VALID [2022-04-27 11:57:58,077 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1066#true} {1066#true} #60#return; {1066#true} is VALID [2022-04-27 11:57:58,077 INFO L272 TraceCheckUtils]: 4: Hoare triple {1066#true} call #t~ret5 := main(); {1066#true} is VALID [2022-04-27 11:57:58,077 INFO L290 TraceCheckUtils]: 5: Hoare triple {1066#true} havoc ~k~0;havoc ~y~0;havoc ~x~0;havoc ~c~0;assume -32768 <= #t~nondet4 && #t~nondet4 <= 32767;~k~0 := #t~nondet4;havoc #t~nondet4; {1066#true} is VALID [2022-04-27 11:57:58,078 INFO L272 TraceCheckUtils]: 6: Hoare triple {1066#true} call assume_abort_if_not((if ~k~0 <= 256 then 1 else 0)); {1066#true} is VALID [2022-04-27 11:57:58,078 INFO L290 TraceCheckUtils]: 7: Hoare triple {1066#true} ~cond := #in~cond; {1066#true} is VALID [2022-04-27 11:57:58,078 INFO L290 TraceCheckUtils]: 8: Hoare triple {1066#true} assume !(0 == ~cond); {1066#true} is VALID [2022-04-27 11:57:58,078 INFO L290 TraceCheckUtils]: 9: Hoare triple {1066#true} assume true; {1066#true} is VALID [2022-04-27 11:57:58,078 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1066#true} {1066#true} #52#return; {1066#true} is VALID [2022-04-27 11:57:58,079 INFO L290 TraceCheckUtils]: 11: Hoare triple {1066#true} ~y~0 := 0;~x~0 := 0;~c~0 := 0; {1104#(and (= main_~c~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:58,079 INFO L290 TraceCheckUtils]: 12: Hoare triple {1104#(and (= main_~c~0 0) (= main_~y~0 0))} assume !false; {1104#(and (= main_~c~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:58,079 INFO L272 TraceCheckUtils]: 13: Hoare triple {1104#(and (= main_~c~0 0) (= main_~y~0 0))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1066#true} is VALID [2022-04-27 11:57:58,079 INFO L290 TraceCheckUtils]: 14: Hoare triple {1066#true} ~cond := #in~cond; {1066#true} is VALID [2022-04-27 11:57:58,079 INFO L290 TraceCheckUtils]: 15: Hoare triple {1066#true} assume !(0 == ~cond); {1066#true} is VALID [2022-04-27 11:57:58,080 INFO L290 TraceCheckUtils]: 16: Hoare triple {1066#true} assume true; {1066#true} is VALID [2022-04-27 11:57:58,080 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {1066#true} {1104#(and (= main_~c~0 0) (= main_~y~0 0))} #54#return; {1104#(and (= main_~c~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:58,081 INFO L290 TraceCheckUtils]: 18: Hoare triple {1104#(and (= main_~c~0 0) (= main_~y~0 0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~y~0 := 1 + ~y~0;~x~0 := ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~x~0; {1126#(and (= main_~y~0 1) (= main_~c~0 1))} is VALID [2022-04-27 11:57:58,081 INFO L290 TraceCheckUtils]: 19: Hoare triple {1126#(and (= main_~y~0 1) (= main_~c~0 1))} assume !false; {1126#(and (= main_~y~0 1) (= main_~c~0 1))} is VALID [2022-04-27 11:57:58,082 INFO L272 TraceCheckUtils]: 20: Hoare triple {1126#(and (= main_~y~0 1) (= main_~c~0 1))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1066#true} is VALID [2022-04-27 11:57:58,082 INFO L290 TraceCheckUtils]: 21: Hoare triple {1066#true} ~cond := #in~cond; {1066#true} is VALID [2022-04-27 11:57:58,082 INFO L290 TraceCheckUtils]: 22: Hoare triple {1066#true} assume !(0 == ~cond); {1066#true} is VALID [2022-04-27 11:57:58,082 INFO L290 TraceCheckUtils]: 23: Hoare triple {1066#true} assume true; {1066#true} is VALID [2022-04-27 11:57:58,083 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {1066#true} {1126#(and (= main_~y~0 1) (= main_~c~0 1))} #54#return; {1126#(and (= main_~y~0 1) (= main_~c~0 1))} is VALID [2022-04-27 11:57:58,083 INFO L290 TraceCheckUtils]: 25: Hoare triple {1126#(and (= main_~y~0 1) (= main_~c~0 1))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~y~0 := 1 + ~y~0;~x~0 := ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~x~0; {1148#(and (< 1 main_~k~0) (= (+ (- 1) main_~y~0) 1) (<= main_~c~0 2))} is VALID [2022-04-27 11:57:58,084 INFO L290 TraceCheckUtils]: 26: Hoare triple {1148#(and (< 1 main_~k~0) (= (+ (- 1) main_~y~0) 1) (<= main_~c~0 2))} assume !false; {1148#(and (< 1 main_~k~0) (= (+ (- 1) main_~y~0) 1) (<= main_~c~0 2))} is VALID [2022-04-27 11:57:58,084 INFO L272 TraceCheckUtils]: 27: Hoare triple {1148#(and (< 1 main_~k~0) (= (+ (- 1) main_~y~0) 1) (<= main_~c~0 2))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1066#true} is VALID [2022-04-27 11:57:58,084 INFO L290 TraceCheckUtils]: 28: Hoare triple {1066#true} ~cond := #in~cond; {1066#true} is VALID [2022-04-27 11:57:58,084 INFO L290 TraceCheckUtils]: 29: Hoare triple {1066#true} assume !(0 == ~cond); {1066#true} is VALID [2022-04-27 11:57:58,084 INFO L290 TraceCheckUtils]: 30: Hoare triple {1066#true} assume true; {1066#true} is VALID [2022-04-27 11:57:58,085 INFO L284 TraceCheckUtils]: 31: Hoare quadruple {1066#true} {1148#(and (< 1 main_~k~0) (= (+ (- 1) main_~y~0) 1) (<= main_~c~0 2))} #54#return; {1148#(and (< 1 main_~k~0) (= (+ (- 1) main_~y~0) 1) (<= main_~c~0 2))} is VALID [2022-04-27 11:57:58,086 INFO L290 TraceCheckUtils]: 32: Hoare triple {1148#(and (< 1 main_~k~0) (= (+ (- 1) main_~y~0) 1) (<= main_~c~0 2))} assume !(~c~0 < ~k~0); {1170#(and (< 1 main_~k~0) (= (+ (- 1) main_~y~0) 1) (<= main_~k~0 2))} is VALID [2022-04-27 11:57:58,086 INFO L272 TraceCheckUtils]: 33: Hoare triple {1170#(and (< 1 main_~k~0) (= (+ (- 1) main_~y~0) 1) (<= main_~k~0 2))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1066#true} is VALID [2022-04-27 11:57:58,086 INFO L290 TraceCheckUtils]: 34: Hoare triple {1066#true} ~cond := #in~cond; {1066#true} is VALID [2022-04-27 11:57:58,086 INFO L290 TraceCheckUtils]: 35: Hoare triple {1066#true} assume !(0 == ~cond); {1066#true} is VALID [2022-04-27 11:57:58,086 INFO L290 TraceCheckUtils]: 36: Hoare triple {1066#true} assume true; {1066#true} is VALID [2022-04-27 11:57:58,087 INFO L284 TraceCheckUtils]: 37: Hoare quadruple {1066#true} {1170#(and (< 1 main_~k~0) (= (+ (- 1) main_~y~0) 1) (<= main_~k~0 2))} #56#return; {1170#(and (< 1 main_~k~0) (= (+ (- 1) main_~y~0) 1) (<= main_~k~0 2))} is VALID [2022-04-27 11:57:58,088 INFO L272 TraceCheckUtils]: 38: Hoare triple {1170#(and (< 1 main_~k~0) (= (+ (- 1) main_~y~0) 1) (<= main_~k~0 2))} call __VERIFIER_assert((if ~k~0 * ~y~0 == ~y~0 * ~y~0 then 1 else 0)); {1189#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-27 11:57:58,089 INFO L290 TraceCheckUtils]: 39: Hoare triple {1189#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1193#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-27 11:57:58,089 INFO L290 TraceCheckUtils]: 40: Hoare triple {1193#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1067#false} is VALID [2022-04-27 11:57:58,089 INFO L290 TraceCheckUtils]: 41: Hoare triple {1067#false} assume !false; {1067#false} is VALID [2022-04-27 11:57:58,089 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 8 proven. 9 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-27 11:57:58,090 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-27 11:57:58,425 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-27 11:57:58,425 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1666547257] [2022-04-27 11:57:58,425 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-27 11:57:58,425 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [633764505] [2022-04-27 11:57:58,425 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [633764505] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-27 11:57:58,425 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-27 11:57:58,425 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-04-27 11:57:58,426 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [489949921] [2022-04-27 11:57:58,426 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-27 11:57:58,426 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 42 [2022-04-27 11:57:58,427 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-27 11:57:58,427 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2022-04-27 11:57:58,458 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 33 edges. 33 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:57:58,459 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-27 11:57:58,459 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-27 11:57:58,459 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-27 11:57:58,459 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-04-27 11:57:58,460 INFO L87 Difference]: Start difference. First operand 35 states and 37 transitions. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2022-04-27 11:57:58,748 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:58,748 INFO L93 Difference]: Finished difference Result 44 states and 48 transitions. [2022-04-27 11:57:58,749 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-27 11:57:58,749 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 42 [2022-04-27 11:57:58,749 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-27 11:57:58,749 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2022-04-27 11:57:58,751 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 44 transitions. [2022-04-27 11:57:58,751 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2022-04-27 11:57:58,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 44 transitions. [2022-04-27 11:57:58,753 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 44 transitions. [2022-04-27 11:57:58,788 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:57:58,790 INFO L225 Difference]: With dead ends: 44 [2022-04-27 11:57:58,790 INFO L226 Difference]: Without dead ends: 38 [2022-04-27 11:57:58,790 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 49 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2022-04-27 11:57:58,791 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 2 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 85 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 86 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 85 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-27 11:57:58,791 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 154 Invalid, 86 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 85 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-27 11:57:58,792 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2022-04-27 11:57:58,802 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2022-04-27 11:57:58,802 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-27 11:57:58,802 INFO L82 GeneralOperation]: Start isEquivalent. First operand 38 states. Second operand has 38 states, 24 states have (on average 1.0416666666666667) internal successors, (25), 24 states have internal predecessors, (25), 9 states have call successors, (9), 6 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-27 11:57:58,802 INFO L74 IsIncluded]: Start isIncluded. First operand 38 states. Second operand has 38 states, 24 states have (on average 1.0416666666666667) internal successors, (25), 24 states have internal predecessors, (25), 9 states have call successors, (9), 6 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-27 11:57:58,803 INFO L87 Difference]: Start difference. First operand 38 states. Second operand has 38 states, 24 states have (on average 1.0416666666666667) internal successors, (25), 24 states have internal predecessors, (25), 9 states have call successors, (9), 6 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-27 11:57:58,804 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:58,804 INFO L93 Difference]: Finished difference Result 38 states and 41 transitions. [2022-04-27 11:57:58,804 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 41 transitions. [2022-04-27 11:57:58,805 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:57:58,805 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:57:58,805 INFO L74 IsIncluded]: Start isIncluded. First operand has 38 states, 24 states have (on average 1.0416666666666667) internal successors, (25), 24 states have internal predecessors, (25), 9 states have call successors, (9), 6 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 38 states. [2022-04-27 11:57:58,805 INFO L87 Difference]: Start difference. First operand has 38 states, 24 states have (on average 1.0416666666666667) internal successors, (25), 24 states have internal predecessors, (25), 9 states have call successors, (9), 6 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 38 states. [2022-04-27 11:57:58,807 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:57:58,807 INFO L93 Difference]: Finished difference Result 38 states and 41 transitions. [2022-04-27 11:57:58,807 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 41 transitions. [2022-04-27 11:57:58,807 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:57:58,807 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:57:58,807 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-27 11:57:58,808 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-27 11:57:58,808 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 24 states have (on average 1.0416666666666667) internal successors, (25), 24 states have internal predecessors, (25), 9 states have call successors, (9), 6 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-27 11:57:58,809 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 41 transitions. [2022-04-27 11:57:58,809 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 41 transitions. Word has length 42 [2022-04-27 11:57:58,809 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-27 11:57:58,809 INFO L495 AbstractCegarLoop]: Abstraction has 38 states and 41 transitions. [2022-04-27 11:57:58,810 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2022-04-27 11:57:58,810 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 41 transitions. [2022-04-27 11:57:58,810 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2022-04-27 11:57:58,810 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 11:57:58,811 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 11:57:58,819 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-27 11:57:59,016 WARN L477 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-27 11:57:59,016 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 11:57:59,016 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 11:57:59,017 INFO L85 PathProgramCache]: Analyzing trace with hash 1951214241, now seen corresponding path program 3 times [2022-04-27 11:57:59,017 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 11:57:59,017 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [984935581] [2022-04-27 11:57:59,017 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 11:57:59,017 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 11:57:59,046 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-27 11:57:59,046 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1643587477] [2022-04-27 11:57:59,046 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-27 11:57:59,047 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-27 11:57:59,047 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-27 11:57:59,052 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-27 11:57:59,060 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-27 11:57:59,493 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-04-27 11:57:59,493 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-27 11:57:59,495 INFO L263 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 20 conjunts are in the unsatisfiable core [2022-04-27 11:57:59,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 11:57:59,512 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-27 11:57:59,881 INFO L272 TraceCheckUtils]: 0: Hoare triple {1459#true} call ULTIMATE.init(); {1459#true} is VALID [2022-04-27 11:57:59,881 INFO L290 TraceCheckUtils]: 1: Hoare triple {1459#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(9, 2);call #Ultimate.allocInit(12, 3); {1459#true} is VALID [2022-04-27 11:57:59,882 INFO L290 TraceCheckUtils]: 2: Hoare triple {1459#true} assume true; {1459#true} is VALID [2022-04-27 11:57:59,882 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1459#true} {1459#true} #60#return; {1459#true} is VALID [2022-04-27 11:57:59,882 INFO L272 TraceCheckUtils]: 4: Hoare triple {1459#true} call #t~ret5 := main(); {1459#true} is VALID [2022-04-27 11:57:59,882 INFO L290 TraceCheckUtils]: 5: Hoare triple {1459#true} havoc ~k~0;havoc ~y~0;havoc ~x~0;havoc ~c~0;assume -32768 <= #t~nondet4 && #t~nondet4 <= 32767;~k~0 := #t~nondet4;havoc #t~nondet4; {1459#true} is VALID [2022-04-27 11:57:59,882 INFO L272 TraceCheckUtils]: 6: Hoare triple {1459#true} call assume_abort_if_not((if ~k~0 <= 256 then 1 else 0)); {1459#true} is VALID [2022-04-27 11:57:59,882 INFO L290 TraceCheckUtils]: 7: Hoare triple {1459#true} ~cond := #in~cond; {1459#true} is VALID [2022-04-27 11:57:59,882 INFO L290 TraceCheckUtils]: 8: Hoare triple {1459#true} assume !(0 == ~cond); {1459#true} is VALID [2022-04-27 11:57:59,882 INFO L290 TraceCheckUtils]: 9: Hoare triple {1459#true} assume true; {1459#true} is VALID [2022-04-27 11:57:59,883 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1459#true} {1459#true} #52#return; {1459#true} is VALID [2022-04-27 11:57:59,883 INFO L290 TraceCheckUtils]: 11: Hoare triple {1459#true} ~y~0 := 0;~x~0 := 0;~c~0 := 0; {1497#(and (= main_~c~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:59,883 INFO L290 TraceCheckUtils]: 12: Hoare triple {1497#(and (= main_~c~0 0) (= main_~y~0 0))} assume !false; {1497#(and (= main_~c~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:59,884 INFO L272 TraceCheckUtils]: 13: Hoare triple {1497#(and (= main_~c~0 0) (= main_~y~0 0))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1459#true} is VALID [2022-04-27 11:57:59,884 INFO L290 TraceCheckUtils]: 14: Hoare triple {1459#true} ~cond := #in~cond; {1459#true} is VALID [2022-04-27 11:57:59,884 INFO L290 TraceCheckUtils]: 15: Hoare triple {1459#true} assume !(0 == ~cond); {1459#true} is VALID [2022-04-27 11:57:59,885 INFO L290 TraceCheckUtils]: 16: Hoare triple {1459#true} assume true; {1459#true} is VALID [2022-04-27 11:57:59,885 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {1459#true} {1497#(and (= main_~c~0 0) (= main_~y~0 0))} #54#return; {1497#(and (= main_~c~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:57:59,889 INFO L290 TraceCheckUtils]: 18: Hoare triple {1497#(and (= main_~c~0 0) (= main_~y~0 0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~y~0 := 1 + ~y~0;~x~0 := ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~x~0; {1519#(and (= (+ (- 1) main_~y~0) 0) (= (+ (- 1) main_~c~0) 0))} is VALID [2022-04-27 11:57:59,890 INFO L290 TraceCheckUtils]: 19: Hoare triple {1519#(and (= (+ (- 1) main_~y~0) 0) (= (+ (- 1) main_~c~0) 0))} assume !false; {1519#(and (= (+ (- 1) main_~y~0) 0) (= (+ (- 1) main_~c~0) 0))} is VALID [2022-04-27 11:57:59,890 INFO L272 TraceCheckUtils]: 20: Hoare triple {1519#(and (= (+ (- 1) main_~y~0) 0) (= (+ (- 1) main_~c~0) 0))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1459#true} is VALID [2022-04-27 11:57:59,890 INFO L290 TraceCheckUtils]: 21: Hoare triple {1459#true} ~cond := #in~cond; {1459#true} is VALID [2022-04-27 11:57:59,890 INFO L290 TraceCheckUtils]: 22: Hoare triple {1459#true} assume !(0 == ~cond); {1459#true} is VALID [2022-04-27 11:57:59,890 INFO L290 TraceCheckUtils]: 23: Hoare triple {1459#true} assume true; {1459#true} is VALID [2022-04-27 11:57:59,891 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {1459#true} {1519#(and (= (+ (- 1) main_~y~0) 0) (= (+ (- 1) main_~c~0) 0))} #54#return; {1519#(and (= (+ (- 1) main_~y~0) 0) (= (+ (- 1) main_~c~0) 0))} is VALID [2022-04-27 11:57:59,891 INFO L290 TraceCheckUtils]: 25: Hoare triple {1519#(and (= (+ (- 1) main_~y~0) 0) (= (+ (- 1) main_~c~0) 0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~y~0 := 1 + ~y~0;~x~0 := ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~x~0; {1541#(and (= (+ (- 2) main_~y~0) 0) (= 0 (+ (- 2) main_~c~0)))} is VALID [2022-04-27 11:57:59,892 INFO L290 TraceCheckUtils]: 26: Hoare triple {1541#(and (= (+ (- 2) main_~y~0) 0) (= 0 (+ (- 2) main_~c~0)))} assume !false; {1541#(and (= (+ (- 2) main_~y~0) 0) (= 0 (+ (- 2) main_~c~0)))} is VALID [2022-04-27 11:57:59,892 INFO L272 TraceCheckUtils]: 27: Hoare triple {1541#(and (= (+ (- 2) main_~y~0) 0) (= 0 (+ (- 2) main_~c~0)))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1459#true} is VALID [2022-04-27 11:57:59,892 INFO L290 TraceCheckUtils]: 28: Hoare triple {1459#true} ~cond := #in~cond; {1459#true} is VALID [2022-04-27 11:57:59,892 INFO L290 TraceCheckUtils]: 29: Hoare triple {1459#true} assume !(0 == ~cond); {1459#true} is VALID [2022-04-27 11:57:59,892 INFO L290 TraceCheckUtils]: 30: Hoare triple {1459#true} assume true; {1459#true} is VALID [2022-04-27 11:57:59,896 INFO L284 TraceCheckUtils]: 31: Hoare quadruple {1459#true} {1541#(and (= (+ (- 2) main_~y~0) 0) (= 0 (+ (- 2) main_~c~0)))} #54#return; {1541#(and (= (+ (- 2) main_~y~0) 0) (= 0 (+ (- 2) main_~c~0)))} is VALID [2022-04-27 11:57:59,897 INFO L290 TraceCheckUtils]: 32: Hoare triple {1541#(and (= (+ (- 2) main_~y~0) 0) (= 0 (+ (- 2) main_~c~0)))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~y~0 := 1 + ~y~0;~x~0 := ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~x~0; {1563#(and (<= main_~c~0 3) (= (+ main_~y~0 (- 3)) 0) (< 2 main_~k~0))} is VALID [2022-04-27 11:57:59,897 INFO L290 TraceCheckUtils]: 33: Hoare triple {1563#(and (<= main_~c~0 3) (= (+ main_~y~0 (- 3)) 0) (< 2 main_~k~0))} assume !false; {1563#(and (<= main_~c~0 3) (= (+ main_~y~0 (- 3)) 0) (< 2 main_~k~0))} is VALID [2022-04-27 11:57:59,897 INFO L272 TraceCheckUtils]: 34: Hoare triple {1563#(and (<= main_~c~0 3) (= (+ main_~y~0 (- 3)) 0) (< 2 main_~k~0))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1459#true} is VALID [2022-04-27 11:57:59,897 INFO L290 TraceCheckUtils]: 35: Hoare triple {1459#true} ~cond := #in~cond; {1459#true} is VALID [2022-04-27 11:57:59,898 INFO L290 TraceCheckUtils]: 36: Hoare triple {1459#true} assume !(0 == ~cond); {1459#true} is VALID [2022-04-27 11:57:59,898 INFO L290 TraceCheckUtils]: 37: Hoare triple {1459#true} assume true; {1459#true} is VALID [2022-04-27 11:57:59,898 INFO L284 TraceCheckUtils]: 38: Hoare quadruple {1459#true} {1563#(and (<= main_~c~0 3) (= (+ main_~y~0 (- 3)) 0) (< 2 main_~k~0))} #54#return; {1563#(and (<= main_~c~0 3) (= (+ main_~y~0 (- 3)) 0) (< 2 main_~k~0))} is VALID [2022-04-27 11:57:59,899 INFO L290 TraceCheckUtils]: 39: Hoare triple {1563#(and (<= main_~c~0 3) (= (+ main_~y~0 (- 3)) 0) (< 2 main_~k~0))} assume !(~c~0 < ~k~0); {1585#(and (<= main_~k~0 3) (= (+ main_~y~0 (- 3)) 0) (< 2 main_~k~0))} is VALID [2022-04-27 11:57:59,899 INFO L272 TraceCheckUtils]: 40: Hoare triple {1585#(and (<= main_~k~0 3) (= (+ main_~y~0 (- 3)) 0) (< 2 main_~k~0))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1459#true} is VALID [2022-04-27 11:57:59,899 INFO L290 TraceCheckUtils]: 41: Hoare triple {1459#true} ~cond := #in~cond; {1459#true} is VALID [2022-04-27 11:57:59,899 INFO L290 TraceCheckUtils]: 42: Hoare triple {1459#true} assume !(0 == ~cond); {1459#true} is VALID [2022-04-27 11:57:59,899 INFO L290 TraceCheckUtils]: 43: Hoare triple {1459#true} assume true; {1459#true} is VALID [2022-04-27 11:57:59,900 INFO L284 TraceCheckUtils]: 44: Hoare quadruple {1459#true} {1585#(and (<= main_~k~0 3) (= (+ main_~y~0 (- 3)) 0) (< 2 main_~k~0))} #56#return; {1585#(and (<= main_~k~0 3) (= (+ main_~y~0 (- 3)) 0) (< 2 main_~k~0))} is VALID [2022-04-27 11:57:59,900 INFO L272 TraceCheckUtils]: 45: Hoare triple {1585#(and (<= main_~k~0 3) (= (+ main_~y~0 (- 3)) 0) (< 2 main_~k~0))} call __VERIFIER_assert((if ~k~0 * ~y~0 == ~y~0 * ~y~0 then 1 else 0)); {1604#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-27 11:57:59,901 INFO L290 TraceCheckUtils]: 46: Hoare triple {1604#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1608#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-27 11:57:59,901 INFO L290 TraceCheckUtils]: 47: Hoare triple {1608#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1460#false} is VALID [2022-04-27 11:57:59,901 INFO L290 TraceCheckUtils]: 48: Hoare triple {1460#false} assume !false; {1460#false} is VALID [2022-04-27 11:57:59,902 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 10 proven. 18 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-27 11:57:59,903 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-27 11:58:00,199 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-27 11:58:00,199 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [984935581] [2022-04-27 11:58:00,199 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-27 11:58:00,200 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1643587477] [2022-04-27 11:58:00,200 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1643587477] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-27 11:58:00,200 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-27 11:58:00,200 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-27 11:58:00,200 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1751937127] [2022-04-27 11:58:00,200 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-27 11:58:00,201 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) Word has length 49 [2022-04-27 11:58:00,201 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-27 11:58:00,202 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2022-04-27 11:58:00,233 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 37 edges. 37 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:58:00,233 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-27 11:58:00,233 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-27 11:58:00,234 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-27 11:58:00,236 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-27 11:58:00,236 INFO L87 Difference]: Start difference. First operand 38 states and 41 transitions. Second operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2022-04-27 11:58:00,602 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:58:00,603 INFO L93 Difference]: Finished difference Result 47 states and 52 transitions. [2022-04-27 11:58:00,603 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-27 11:58:00,603 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) Word has length 49 [2022-04-27 11:58:00,603 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-27 11:58:00,604 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2022-04-27 11:58:00,605 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 48 transitions. [2022-04-27 11:58:00,605 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2022-04-27 11:58:00,607 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 48 transitions. [2022-04-27 11:58:00,607 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 9 states and 48 transitions. [2022-04-27 11:58:00,650 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 48 edges. 48 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:58:00,652 INFO L225 Difference]: With dead ends: 47 [2022-04-27 11:58:00,652 INFO L226 Difference]: Without dead ends: 41 [2022-04-27 11:58:00,652 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 55 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2022-04-27 11:58:00,653 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 2 mSDsluCounter, 151 mSDsCounter, 0 mSdLazyCounter, 119 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 185 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 119 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-27 11:58:00,653 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 185 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 119 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-27 11:58:00,654 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-04-27 11:58:00,669 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-04-27 11:58:00,669 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-27 11:58:00,670 INFO L82 GeneralOperation]: Start isEquivalent. First operand 41 states. Second operand has 41 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 10 states have call successors, (10), 6 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-27 11:58:00,670 INFO L74 IsIncluded]: Start isIncluded. First operand 41 states. Second operand has 41 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 10 states have call successors, (10), 6 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-27 11:58:00,670 INFO L87 Difference]: Start difference. First operand 41 states. Second operand has 41 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 10 states have call successors, (10), 6 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-27 11:58:00,672 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:58:00,672 INFO L93 Difference]: Finished difference Result 41 states and 45 transitions. [2022-04-27 11:58:00,672 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-27 11:58:00,672 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:58:00,672 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:58:00,673 INFO L74 IsIncluded]: Start isIncluded. First operand has 41 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 10 states have call successors, (10), 6 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 41 states. [2022-04-27 11:58:00,673 INFO L87 Difference]: Start difference. First operand has 41 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 10 states have call successors, (10), 6 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 41 states. [2022-04-27 11:58:00,675 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:58:00,675 INFO L93 Difference]: Finished difference Result 41 states and 45 transitions. [2022-04-27 11:58:00,675 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-27 11:58:00,675 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:58:00,675 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:58:00,675 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-27 11:58:00,675 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-27 11:58:00,677 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 10 states have call successors, (10), 6 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-27 11:58:00,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 45 transitions. [2022-04-27 11:58:00,679 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 45 transitions. Word has length 49 [2022-04-27 11:58:00,679 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-27 11:58:00,679 INFO L495 AbstractCegarLoop]: Abstraction has 41 states and 45 transitions. [2022-04-27 11:58:00,679 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2022-04-27 11:58:00,679 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-27 11:58:00,681 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-04-27 11:58:00,681 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 11:58:00,681 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 11:58:00,691 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-27 11:58:00,887 WARN L477 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-27 11:58:00,887 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 11:58:00,889 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 11:58:00,889 INFO L85 PathProgramCache]: Analyzing trace with hash 327675008, now seen corresponding path program 4 times [2022-04-27 11:58:00,894 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 11:58:00,894 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [871117464] [2022-04-27 11:58:00,894 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 11:58:00,894 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 11:58:00,907 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-27 11:58:00,908 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [898008398] [2022-04-27 11:58:00,908 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-27 11:58:00,908 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-27 11:58:00,908 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-27 11:58:00,909 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-27 11:58:00,917 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-27 11:58:00,960 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-27 11:58:00,960 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-27 11:58:00,961 INFO L263 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 24 conjunts are in the unsatisfiable core [2022-04-27 11:58:00,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 11:58:00,980 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-27 11:58:01,317 INFO L272 TraceCheckUtils]: 0: Hoare triple {1890#true} call ULTIMATE.init(); {1890#true} is VALID [2022-04-27 11:58:01,318 INFO L290 TraceCheckUtils]: 1: Hoare triple {1890#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(9, 2);call #Ultimate.allocInit(12, 3); {1890#true} is VALID [2022-04-27 11:58:01,318 INFO L290 TraceCheckUtils]: 2: Hoare triple {1890#true} assume true; {1890#true} is VALID [2022-04-27 11:58:01,318 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1890#true} {1890#true} #60#return; {1890#true} is VALID [2022-04-27 11:58:01,318 INFO L272 TraceCheckUtils]: 4: Hoare triple {1890#true} call #t~ret5 := main(); {1890#true} is VALID [2022-04-27 11:58:01,318 INFO L290 TraceCheckUtils]: 5: Hoare triple {1890#true} havoc ~k~0;havoc ~y~0;havoc ~x~0;havoc ~c~0;assume -32768 <= #t~nondet4 && #t~nondet4 <= 32767;~k~0 := #t~nondet4;havoc #t~nondet4; {1890#true} is VALID [2022-04-27 11:58:01,318 INFO L272 TraceCheckUtils]: 6: Hoare triple {1890#true} call assume_abort_if_not((if ~k~0 <= 256 then 1 else 0)); {1890#true} is VALID [2022-04-27 11:58:01,318 INFO L290 TraceCheckUtils]: 7: Hoare triple {1890#true} ~cond := #in~cond; {1890#true} is VALID [2022-04-27 11:58:01,319 INFO L290 TraceCheckUtils]: 8: Hoare triple {1890#true} assume !(0 == ~cond); {1890#true} is VALID [2022-04-27 11:58:01,319 INFO L290 TraceCheckUtils]: 9: Hoare triple {1890#true} assume true; {1890#true} is VALID [2022-04-27 11:58:01,319 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1890#true} {1890#true} #52#return; {1890#true} is VALID [2022-04-27 11:58:01,319 INFO L290 TraceCheckUtils]: 11: Hoare triple {1890#true} ~y~0 := 0;~x~0 := 0;~c~0 := 0; {1928#(and (= main_~c~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:58:01,320 INFO L290 TraceCheckUtils]: 12: Hoare triple {1928#(and (= main_~c~0 0) (= main_~y~0 0))} assume !false; {1928#(and (= main_~c~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:58:01,320 INFO L272 TraceCheckUtils]: 13: Hoare triple {1928#(and (= main_~c~0 0) (= main_~y~0 0))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1890#true} is VALID [2022-04-27 11:58:01,320 INFO L290 TraceCheckUtils]: 14: Hoare triple {1890#true} ~cond := #in~cond; {1890#true} is VALID [2022-04-27 11:58:01,320 INFO L290 TraceCheckUtils]: 15: Hoare triple {1890#true} assume !(0 == ~cond); {1890#true} is VALID [2022-04-27 11:58:01,320 INFO L290 TraceCheckUtils]: 16: Hoare triple {1890#true} assume true; {1890#true} is VALID [2022-04-27 11:58:01,321 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {1890#true} {1928#(and (= main_~c~0 0) (= main_~y~0 0))} #54#return; {1928#(and (= main_~c~0 0) (= main_~y~0 0))} is VALID [2022-04-27 11:58:01,321 INFO L290 TraceCheckUtils]: 18: Hoare triple {1928#(and (= main_~c~0 0) (= main_~y~0 0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~y~0 := 1 + ~y~0;~x~0 := ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~x~0; {1950#(and (= (+ (- 1) main_~c~0) 0) (= main_~y~0 1))} is VALID [2022-04-27 11:58:01,322 INFO L290 TraceCheckUtils]: 19: Hoare triple {1950#(and (= (+ (- 1) main_~c~0) 0) (= main_~y~0 1))} assume !false; {1950#(and (= (+ (- 1) main_~c~0) 0) (= main_~y~0 1))} is VALID [2022-04-27 11:58:01,322 INFO L272 TraceCheckUtils]: 20: Hoare triple {1950#(and (= (+ (- 1) main_~c~0) 0) (= main_~y~0 1))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1890#true} is VALID [2022-04-27 11:58:01,322 INFO L290 TraceCheckUtils]: 21: Hoare triple {1890#true} ~cond := #in~cond; {1890#true} is VALID [2022-04-27 11:58:01,322 INFO L290 TraceCheckUtils]: 22: Hoare triple {1890#true} assume !(0 == ~cond); {1890#true} is VALID [2022-04-27 11:58:01,322 INFO L290 TraceCheckUtils]: 23: Hoare triple {1890#true} assume true; {1890#true} is VALID [2022-04-27 11:58:01,323 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {1890#true} {1950#(and (= (+ (- 1) main_~c~0) 0) (= main_~y~0 1))} #54#return; {1950#(and (= (+ (- 1) main_~c~0) 0) (= main_~y~0 1))} is VALID [2022-04-27 11:58:01,323 INFO L290 TraceCheckUtils]: 25: Hoare triple {1950#(and (= (+ (- 1) main_~c~0) 0) (= main_~y~0 1))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~y~0 := 1 + ~y~0;~x~0 := ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~x~0; {1972#(and (= (+ (- 1) main_~y~0) 1) (= 0 (+ (- 2) main_~c~0)))} is VALID [2022-04-27 11:58:01,324 INFO L290 TraceCheckUtils]: 26: Hoare triple {1972#(and (= (+ (- 1) main_~y~0) 1) (= 0 (+ (- 2) main_~c~0)))} assume !false; {1972#(and (= (+ (- 1) main_~y~0) 1) (= 0 (+ (- 2) main_~c~0)))} is VALID [2022-04-27 11:58:01,324 INFO L272 TraceCheckUtils]: 27: Hoare triple {1972#(and (= (+ (- 1) main_~y~0) 1) (= 0 (+ (- 2) main_~c~0)))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1890#true} is VALID [2022-04-27 11:58:01,324 INFO L290 TraceCheckUtils]: 28: Hoare triple {1890#true} ~cond := #in~cond; {1890#true} is VALID [2022-04-27 11:58:01,324 INFO L290 TraceCheckUtils]: 29: Hoare triple {1890#true} assume !(0 == ~cond); {1890#true} is VALID [2022-04-27 11:58:01,324 INFO L290 TraceCheckUtils]: 30: Hoare triple {1890#true} assume true; {1890#true} is VALID [2022-04-27 11:58:01,325 INFO L284 TraceCheckUtils]: 31: Hoare quadruple {1890#true} {1972#(and (= (+ (- 1) main_~y~0) 1) (= 0 (+ (- 2) main_~c~0)))} #54#return; {1972#(and (= (+ (- 1) main_~y~0) 1) (= 0 (+ (- 2) main_~c~0)))} is VALID [2022-04-27 11:58:01,326 INFO L290 TraceCheckUtils]: 32: Hoare triple {1972#(and (= (+ (- 1) main_~y~0) 1) (= 0 (+ (- 2) main_~c~0)))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~y~0 := 1 + ~y~0;~x~0 := ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~x~0; {1994#(and (= (+ (- 2) main_~y~0) 1) (= (+ main_~c~0 (- 3)) 0))} is VALID [2022-04-27 11:58:01,328 INFO L290 TraceCheckUtils]: 33: Hoare triple {1994#(and (= (+ (- 2) main_~y~0) 1) (= (+ main_~c~0 (- 3)) 0))} assume !false; {1994#(and (= (+ (- 2) main_~y~0) 1) (= (+ main_~c~0 (- 3)) 0))} is VALID [2022-04-27 11:58:01,328 INFO L272 TraceCheckUtils]: 34: Hoare triple {1994#(and (= (+ (- 2) main_~y~0) 1) (= (+ main_~c~0 (- 3)) 0))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1890#true} is VALID [2022-04-27 11:58:01,328 INFO L290 TraceCheckUtils]: 35: Hoare triple {1890#true} ~cond := #in~cond; {1890#true} is VALID [2022-04-27 11:58:01,329 INFO L290 TraceCheckUtils]: 36: Hoare triple {1890#true} assume !(0 == ~cond); {1890#true} is VALID [2022-04-27 11:58:01,329 INFO L290 TraceCheckUtils]: 37: Hoare triple {1890#true} assume true; {1890#true} is VALID [2022-04-27 11:58:01,330 INFO L284 TraceCheckUtils]: 38: Hoare quadruple {1890#true} {1994#(and (= (+ (- 2) main_~y~0) 1) (= (+ main_~c~0 (- 3)) 0))} #54#return; {1994#(and (= (+ (- 2) main_~y~0) 1) (= (+ main_~c~0 (- 3)) 0))} is VALID [2022-04-27 11:58:01,331 INFO L290 TraceCheckUtils]: 39: Hoare triple {1994#(and (= (+ (- 2) main_~y~0) 1) (= (+ main_~c~0 (- 3)) 0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~y~0 := 1 + ~y~0;~x~0 := ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~x~0; {2016#(and (= main_~y~0 4) (< 3 main_~k~0) (<= main_~c~0 4))} is VALID [2022-04-27 11:58:01,334 INFO L290 TraceCheckUtils]: 40: Hoare triple {2016#(and (= main_~y~0 4) (< 3 main_~k~0) (<= main_~c~0 4))} assume !false; {2016#(and (= main_~y~0 4) (< 3 main_~k~0) (<= main_~c~0 4))} is VALID [2022-04-27 11:58:01,334 INFO L272 TraceCheckUtils]: 41: Hoare triple {2016#(and (= main_~y~0 4) (< 3 main_~k~0) (<= main_~c~0 4))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1890#true} is VALID [2022-04-27 11:58:01,334 INFO L290 TraceCheckUtils]: 42: Hoare triple {1890#true} ~cond := #in~cond; {1890#true} is VALID [2022-04-27 11:58:01,334 INFO L290 TraceCheckUtils]: 43: Hoare triple {1890#true} assume !(0 == ~cond); {1890#true} is VALID [2022-04-27 11:58:01,334 INFO L290 TraceCheckUtils]: 44: Hoare triple {1890#true} assume true; {1890#true} is VALID [2022-04-27 11:58:01,335 INFO L284 TraceCheckUtils]: 45: Hoare quadruple {1890#true} {2016#(and (= main_~y~0 4) (< 3 main_~k~0) (<= main_~c~0 4))} #54#return; {2016#(and (= main_~y~0 4) (< 3 main_~k~0) (<= main_~c~0 4))} is VALID [2022-04-27 11:58:01,336 INFO L290 TraceCheckUtils]: 46: Hoare triple {2016#(and (= main_~y~0 4) (< 3 main_~k~0) (<= main_~c~0 4))} assume !(~c~0 < ~k~0); {2038#(and (= main_~y~0 4) (< 3 main_~k~0) (<= main_~k~0 4))} is VALID [2022-04-27 11:58:01,336 INFO L272 TraceCheckUtils]: 47: Hoare triple {2038#(and (= main_~y~0 4) (< 3 main_~k~0) (<= main_~k~0 4))} call __VERIFIER_assert((if 0 == -2 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 6 * ~y~0 * ~y~0 * ~y~0 * ~y~0 * ~y~0 - 5 * ~y~0 * ~y~0 * ~y~0 * ~y~0 + ~y~0 * ~y~0 + 12 * ~x~0 then 1 else 0)); {1890#true} is VALID [2022-04-27 11:58:01,336 INFO L290 TraceCheckUtils]: 48: Hoare triple {1890#true} ~cond := #in~cond; {1890#true} is VALID [2022-04-27 11:58:01,336 INFO L290 TraceCheckUtils]: 49: Hoare triple {1890#true} assume !(0 == ~cond); {1890#true} is VALID [2022-04-27 11:58:01,336 INFO L290 TraceCheckUtils]: 50: Hoare triple {1890#true} assume true; {1890#true} is VALID [2022-04-27 11:58:01,337 INFO L284 TraceCheckUtils]: 51: Hoare quadruple {1890#true} {2038#(and (= main_~y~0 4) (< 3 main_~k~0) (<= main_~k~0 4))} #56#return; {2038#(and (= main_~y~0 4) (< 3 main_~k~0) (<= main_~k~0 4))} is VALID [2022-04-27 11:58:01,337 INFO L272 TraceCheckUtils]: 52: Hoare triple {2038#(and (= main_~y~0 4) (< 3 main_~k~0) (<= main_~k~0 4))} call __VERIFIER_assert((if ~k~0 * ~y~0 == ~y~0 * ~y~0 then 1 else 0)); {2057#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-27 11:58:01,338 INFO L290 TraceCheckUtils]: 53: Hoare triple {2057#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {2061#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-27 11:58:01,339 INFO L290 TraceCheckUtils]: 54: Hoare triple {2061#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1891#false} is VALID [2022-04-27 11:58:01,339 INFO L290 TraceCheckUtils]: 55: Hoare triple {1891#false} assume !false; {1891#false} is VALID [2022-04-27 11:58:01,339 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 12 proven. 30 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-27 11:58:01,339 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-27 11:58:01,655 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-27 11:58:01,655 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [871117464] [2022-04-27 11:58:01,655 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-27 11:58:01,655 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [898008398] [2022-04-27 11:58:01,656 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [898008398] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-27 11:58:01,656 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-27 11:58:01,656 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-04-27 11:58:01,656 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2132500441] [2022-04-27 11:58:01,656 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-27 11:58:01,657 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) Word has length 56 [2022-04-27 11:58:01,657 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-27 11:58:01,657 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2022-04-27 11:58:01,687 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 41 edges. 41 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:58:01,687 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-27 11:58:01,687 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-27 11:58:01,688 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-27 11:58:01,688 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2022-04-27 11:58:01,688 INFO L87 Difference]: Start difference. First operand 41 states and 45 transitions. Second operand has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2022-04-27 11:58:02,121 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:58:02,121 INFO L93 Difference]: Finished difference Result 50 states and 56 transitions. [2022-04-27 11:58:02,121 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-27 11:58:02,121 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) Word has length 56 [2022-04-27 11:58:02,122 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-27 11:58:02,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2022-04-27 11:58:02,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 52 transitions. [2022-04-27 11:58:02,124 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2022-04-27 11:58:02,125 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 52 transitions. [2022-04-27 11:58:02,125 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 10 states and 52 transitions. [2022-04-27 11:58:02,171 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 52 edges. 52 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 11:58:02,173 INFO L225 Difference]: With dead ends: 50 [2022-04-27 11:58:02,173 INFO L226 Difference]: Without dead ends: 44 [2022-04-27 11:58:02,173 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 61 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2022-04-27 11:58:02,174 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 2 mSDsluCounter, 181 mSDsCounter, 0 mSdLazyCounter, 159 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 218 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 159 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-27 11:58:02,174 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 218 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 159 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-27 11:58:02,175 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-27 11:58:02,195 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 44. [2022-04-27 11:58:02,195 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-27 11:58:02,195 INFO L82 GeneralOperation]: Start isEquivalent. First operand 44 states. Second operand has 44 states, 28 states have (on average 1.0357142857142858) internal successors, (29), 28 states have internal predecessors, (29), 11 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-27 11:58:02,196 INFO L74 IsIncluded]: Start isIncluded. First operand 44 states. Second operand has 44 states, 28 states have (on average 1.0357142857142858) internal successors, (29), 28 states have internal predecessors, (29), 11 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-27 11:58:02,196 INFO L87 Difference]: Start difference. First operand 44 states. Second operand has 44 states, 28 states have (on average 1.0357142857142858) internal successors, (29), 28 states have internal predecessors, (29), 11 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-27 11:58:02,199 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:58:02,199 INFO L93 Difference]: Finished difference Result 44 states and 49 transitions. [2022-04-27 11:58:02,199 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 49 transitions. [2022-04-27 11:58:02,199 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:58:02,199 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:58:02,200 INFO L74 IsIncluded]: Start isIncluded. First operand has 44 states, 28 states have (on average 1.0357142857142858) internal successors, (29), 28 states have internal predecessors, (29), 11 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 44 states. [2022-04-27 11:58:02,200 INFO L87 Difference]: Start difference. First operand has 44 states, 28 states have (on average 1.0357142857142858) internal successors, (29), 28 states have internal predecessors, (29), 11 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 44 states. [2022-04-27 11:58:02,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 11:58:02,202 INFO L93 Difference]: Finished difference Result 44 states and 49 transitions. [2022-04-27 11:58:02,202 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 49 transitions. [2022-04-27 11:58:02,202 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 11:58:02,202 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 11:58:02,202 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-27 11:58:02,202 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-27 11:58:02,202 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 28 states have (on average 1.0357142857142858) internal successors, (29), 28 states have internal predecessors, (29), 11 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-27 11:58:02,204 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 49 transitions. [2022-04-27 11:58:02,204 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 49 transitions. Word has length 56 [2022-04-27 11:58:02,204 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-27 11:58:02,204 INFO L495 AbstractCegarLoop]: Abstraction has 44 states and 49 transitions. [2022-04-27 11:58:02,204 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2022-04-27 11:58:02,204 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 49 transitions. [2022-04-27 11:58:02,206 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2022-04-27 11:58:02,206 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 11:58:02,206 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 11:58:02,233 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-27 11:58:02,426 WARN L477 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-27 11:58:02,426 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 11:58:02,426 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 11:58:02,427 INFO L85 PathProgramCache]: Analyzing trace with hash -16244287, now seen corresponding path program 5 times [2022-04-27 11:58:02,427 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 11:58:02,427 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [558851756] [2022-04-27 11:58:02,427 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 11:58:02,427 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 11:58:02,439 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-27 11:58:02,439 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1502174657] [2022-04-27 11:58:02,439 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-04-27 11:58:02,439 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-27 11:58:02,439 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-27 11:58:02,440 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-27 11:58:02,460 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process