./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound20.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version a31fd051 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound20.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 1fbe6596ea58bb65874b731661e9f9f596a91893af06dcebaa497157579c7f46 --- Real Ultimate output --- This is Ultimate 0.2.2-?-a31fd05 [2023-02-15 12:28:16,969 INFO L177 SettingsManager]: Resetting all preferences to default values... [2023-02-15 12:28:16,970 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2023-02-15 12:28:16,995 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2023-02-15 12:28:16,997 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2023-02-15 12:28:16,999 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2023-02-15 12:28:17,000 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2023-02-15 12:28:17,003 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2023-02-15 12:28:17,004 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2023-02-15 12:28:17,007 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2023-02-15 12:28:17,008 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2023-02-15 12:28:17,010 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2023-02-15 12:28:17,010 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2023-02-15 12:28:17,012 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2023-02-15 12:28:17,013 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2023-02-15 12:28:17,015 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2023-02-15 12:28:17,015 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2023-02-15 12:28:17,016 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2023-02-15 12:28:17,017 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2023-02-15 12:28:17,021 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2023-02-15 12:28:17,022 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2023-02-15 12:28:17,022 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2023-02-15 12:28:17,023 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2023-02-15 12:28:17,024 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2023-02-15 12:28:17,029 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2023-02-15 12:28:17,030 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2023-02-15 12:28:17,030 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2023-02-15 12:28:17,031 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2023-02-15 12:28:17,031 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2023-02-15 12:28:17,032 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2023-02-15 12:28:17,032 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2023-02-15 12:28:17,033 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2023-02-15 12:28:17,034 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2023-02-15 12:28:17,035 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2023-02-15 12:28:17,036 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2023-02-15 12:28:17,037 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2023-02-15 12:28:17,037 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2023-02-15 12:28:17,038 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2023-02-15 12:28:17,038 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2023-02-15 12:28:17,039 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2023-02-15 12:28:17,039 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2023-02-15 12:28:17,040 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2023-02-15 12:28:17,065 INFO L113 SettingsManager]: Loading preferences was successful [2023-02-15 12:28:17,065 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2023-02-15 12:28:17,065 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-02-15 12:28:17,066 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-02-15 12:28:17,066 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-02-15 12:28:17,066 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-02-15 12:28:17,067 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-02-15 12:28:17,067 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2023-02-15 12:28:17,067 INFO L138 SettingsManager]: * Use SBE=true [2023-02-15 12:28:17,067 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-02-15 12:28:17,068 INFO L138 SettingsManager]: * sizeof long=4 [2023-02-15 12:28:17,068 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2023-02-15 12:28:17,068 INFO L138 SettingsManager]: * sizeof POINTER=4 [2023-02-15 12:28:17,068 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2023-02-15 12:28:17,069 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-02-15 12:28:17,069 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-02-15 12:28:17,069 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-02-15 12:28:17,069 INFO L138 SettingsManager]: * sizeof long double=12 [2023-02-15 12:28:17,069 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2023-02-15 12:28:17,069 INFO L138 SettingsManager]: * Use constant arrays=true [2023-02-15 12:28:17,070 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-02-15 12:28:17,070 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-02-15 12:28:17,070 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-02-15 12:28:17,070 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2023-02-15 12:28:17,070 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-02-15 12:28:17,070 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-02-15 12:28:17,071 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-02-15 12:28:17,071 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-02-15 12:28:17,071 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2023-02-15 12:28:17,071 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-02-15 12:28:17,071 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-02-15 12:28:17,071 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-02-15 12:28:17,072 INFO L138 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-02-15 12:28:17,072 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-02-15 12:28:17,072 INFO L138 SettingsManager]: * Independence relation used for large block encoding in concurrent analysis=SYNTACTIC [2023-02-15 12:28:17,072 INFO L138 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC 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.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 1fbe6596ea58bb65874b731661e9f9f596a91893af06dcebaa497157579c7f46 [2023-02-15 12:28:17,267 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-02-15 12:28:17,287 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-02-15 12:28:17,289 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-02-15 12:28:17,289 INFO L271 PluginConnector]: Initializing CDTParser... [2023-02-15 12:28:17,290 INFO L275 PluginConnector]: CDTParser initialized [2023-02-15 12:28:17,290 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound20.c [2023-02-15 12:28:18,225 INFO L500 CDTParser]: Created temporary CDT project at NULL [2023-02-15 12:28:18,336 INFO L351 CDTParser]: Found 1 translation units. [2023-02-15 12:28:18,336 INFO L172 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound20.c [2023-02-15 12:28:18,340 INFO L394 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d22368c27/7b0911ab4377409da38f49e0487fdcda/FLAG8834c45a5 [2023-02-15 12:28:18,352 INFO L402 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d22368c27/7b0911ab4377409da38f49e0487fdcda [2023-02-15 12:28:18,353 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-02-15 12:28:18,354 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2023-02-15 12:28:18,356 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-02-15 12:28:18,356 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-02-15 12:28:18,359 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2023-02-15 12:28:18,360 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.02 12:28:18" (1/1) ... [2023-02-15 12:28:18,360 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@58ec3c6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18, skipping insertion in model container [2023-02-15 12:28:18,361 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.02 12:28:18" (1/1) ... [2023-02-15 12:28:18,365 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2023-02-15 12:28:18,379 INFO L178 MainTranslator]: Built tables and reachable declarations [2023-02-15 12:28:18,499 WARN L237 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound20.c[458,471] [2023-02-15 12:28:18,507 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-15 12:28:18,515 INFO L203 MainTranslator]: Completed pre-run [2023-02-15 12:28:18,522 WARN L237 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound20.c[458,471] [2023-02-15 12:28:18,525 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-15 12:28:18,533 INFO L208 MainTranslator]: Completed translation [2023-02-15 12:28:18,533 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18 WrapperNode [2023-02-15 12:28:18,533 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-02-15 12:28:18,534 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-02-15 12:28:18,534 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-02-15 12:28:18,534 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2023-02-15 12:28:18,538 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18" (1/1) ... [2023-02-15 12:28:18,544 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18" (1/1) ... [2023-02-15 12:28:18,554 INFO L138 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 38 [2023-02-15 12:28:18,554 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-02-15 12:28:18,555 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-02-15 12:28:18,555 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2023-02-15 12:28:18,555 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2023-02-15 12:28:18,560 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18" (1/1) ... [2023-02-15 12:28:18,560 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18" (1/1) ... [2023-02-15 12:28:18,561 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18" (1/1) ... [2023-02-15 12:28:18,561 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18" (1/1) ... [2023-02-15 12:28:18,562 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18" (1/1) ... [2023-02-15 12:28:18,564 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18" (1/1) ... [2023-02-15 12:28:18,565 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18" (1/1) ... [2023-02-15 12:28:18,565 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18" (1/1) ... [2023-02-15 12:28:18,566 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-02-15 12:28:18,566 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-02-15 12:28:18,567 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2023-02-15 12:28:18,567 INFO L275 PluginConnector]: RCFGBuilder initialized [2023-02-15 12:28:18,567 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18" (1/1) ... [2023-02-15 12:28:18,576 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-02-15 12:28:18,582 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:28:18,591 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) [2023-02-15 12:28:18,595 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 [2023-02-15 12:28:18,614 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-02-15 12:28:18,614 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-02-15 12:28:18,614 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-02-15 12:28:18,614 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-02-15 12:28:18,615 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-02-15 12:28:18,615 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-02-15 12:28:18,652 INFO L235 CfgBuilder]: Building ICFG [2023-02-15 12:28:18,653 INFO L261 CfgBuilder]: Building CFG for each procedure with an implementation [2023-02-15 12:28:18,729 INFO L276 CfgBuilder]: Performing block encoding [2023-02-15 12:28:18,732 INFO L295 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-02-15 12:28:18,733 INFO L300 CfgBuilder]: Removed 1 assume(true) statements. [2023-02-15 12:28:18,734 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.02 12:28:18 BoogieIcfgContainer [2023-02-15 12:28:18,734 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-02-15 12:28:18,735 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-02-15 12:28:18,735 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2023-02-15 12:28:18,737 INFO L275 PluginConnector]: TraceAbstraction initialized [2023-02-15 12:28:18,737 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.02 12:28:18" (1/3) ... [2023-02-15 12:28:18,738 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@428803cd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.02 12:28:18, skipping insertion in model container [2023-02-15 12:28:18,738 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:28:18" (2/3) ... [2023-02-15 12:28:18,738 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@428803cd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.02 12:28:18, skipping insertion in model container [2023-02-15 12:28:18,738 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.02 12:28:18" (3/3) ... [2023-02-15 12:28:18,739 INFO L112 eAbstractionObserver]: Analyzing ICFG ps4-ll_valuebound20.c [2023-02-15 12:28:18,749 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-02-15 12:28:18,750 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-02-15 12:28:18,776 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-02-15 12:28:18,780 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=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@1a507297, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-02-15 12:28:18,780 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-02-15 12:28:18,783 INFO L276 IsEmpty]: Start isEmpty. Operand has 19 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 14 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-02-15 12:28:18,787 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-02-15 12:28:18,787 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:28:18,787 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:28:18,788 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:28:18,791 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:28:18,791 INFO L85 PathProgramCache]: Analyzing trace with hash -589436290, now seen corresponding path program 1 times [2023-02-15 12:28:18,796 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:28:18,796 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1724822717] [2023-02-15 12:28:18,796 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:28:18,797 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:28:18,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:28:18,860 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:28:18,860 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1724822717] [2023-02-15 12:28:18,861 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-02-15 12:28:18,861 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1234456492] [2023-02-15 12:28:18,861 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:28:18,861 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:28:18,861 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:28:18,864 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:28:18,865 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-02-15 12:28:18,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:28:18,898 INFO L263 TraceCheckSpWp]: Trace formula consists of 48 conjuncts, 1 conjunts are in the unsatisfiable core [2023-02-15 12:28:18,901 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:28:18,913 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-15 12:28:18,913 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 12:28:18,914 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1234456492] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 12:28:18,914 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 12:28:18,914 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-02-15 12:28:18,915 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1202363813] [2023-02-15 12:28:18,916 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 12:28:18,918 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-02-15 12:28:18,918 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:28:18,939 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-02-15 12:28:18,940 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-02-15 12:28:18,941 INFO L87 Difference]: Start difference. First operand has 19 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 14 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-02-15 12:28:18,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:28:18,966 INFO L93 Difference]: Finished difference Result 35 states and 49 transitions. [2023-02-15 12:28:18,977 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-02-15 12:28:18,978 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2023-02-15 12:28:18,986 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:28:19,000 INFO L225 Difference]: With dead ends: 35 [2023-02-15 12:28:19,001 INFO L226 Difference]: Without dead ends: 15 [2023-02-15 12:28:19,003 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-02-15 12:28:19,005 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 21 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 12:28:19,007 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 12:28:19,017 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2023-02-15 12:28:19,025 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2023-02-15 12:28:19,026 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 10 states have (on average 1.2) internal successors, (12), 11 states have internal predecessors, (12), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-02-15 12:28:19,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 17 transitions. [2023-02-15 12:28:19,028 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 17 transitions. Word has length 9 [2023-02-15 12:28:19,029 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:28:19,029 INFO L495 AbstractCegarLoop]: Abstraction has 15 states and 17 transitions. [2023-02-15 12:28:19,029 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-02-15 12:28:19,030 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 17 transitions. [2023-02-15 12:28:19,030 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-02-15 12:28:19,031 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:28:19,031 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:28:19,051 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-02-15 12:28:19,235 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-02-15 12:28:19,236 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:28:19,238 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:28:19,238 INFO L85 PathProgramCache]: Analyzing trace with hash 1187358532, now seen corresponding path program 1 times [2023-02-15 12:28:19,238 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:28:19,238 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [548982072] [2023-02-15 12:28:19,239 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:28:19,239 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:28:19,258 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:28:19,260 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [586324098] [2023-02-15 12:28:19,260 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:28:19,260 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:28:19,260 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:28:19,261 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) [2023-02-15 12:28:19,269 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-02-15 12:28:19,324 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:28:19,325 INFO L263 TraceCheckSpWp]: Trace formula consists of 48 conjuncts, 10 conjunts are in the unsatisfiable core [2023-02-15 12:28:19,326 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:28:19,391 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-15 12:28:19,392 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 12:28:19,398 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:28:19,399 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [548982072] [2023-02-15 12:28:19,399 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:28:19,399 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [586324098] [2023-02-15 12:28:19,399 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [586324098] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 12:28:19,399 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 12:28:19,399 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-02-15 12:28:19,400 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [899879014] [2023-02-15 12:28:19,400 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 12:28:19,400 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-15 12:28:19,400 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:28:19,401 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-15 12:28:19,401 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-02-15 12:28:19,401 INFO L87 Difference]: Start difference. First operand 15 states and 17 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-02-15 12:28:19,439 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:28:19,439 INFO L93 Difference]: Finished difference Result 26 states and 30 transitions. [2023-02-15 12:28:19,440 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-02-15 12:28:19,440 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2023-02-15 12:28:19,440 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:28:19,440 INFO L225 Difference]: With dead ends: 26 [2023-02-15 12:28:19,440 INFO L226 Difference]: Without dead ends: 22 [2023-02-15 12:28:19,441 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-02-15 12:28:19,442 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 6 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 45 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 [2023-02-15 12:28:19,442 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 45 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 12:28:19,443 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2023-02-15 12:28:19,446 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2023-02-15 12:28:19,446 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-02-15 12:28:19,447 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 24 transitions. [2023-02-15 12:28:19,447 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 24 transitions. Word has length 9 [2023-02-15 12:28:19,447 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:28:19,447 INFO L495 AbstractCegarLoop]: Abstraction has 22 states and 24 transitions. [2023-02-15 12:28:19,447 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-02-15 12:28:19,447 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 24 transitions. [2023-02-15 12:28:19,448 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2023-02-15 12:28:19,448 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:28:19,448 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:28:19,452 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-02-15 12:28:19,652 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,SelfDestructingSolverStorable1 [2023-02-15 12:28:19,653 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:28:19,653 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:28:19,653 INFO L85 PathProgramCache]: Analyzing trace with hash -1781398469, now seen corresponding path program 1 times [2023-02-15 12:28:19,654 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:28:19,654 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [992286666] [2023-02-15 12:28:19,654 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:28:19,654 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:28:19,662 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:28:19,662 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [133144675] [2023-02-15 12:28:19,663 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:28:19,663 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:28:19,663 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:28:19,664 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) [2023-02-15 12:28:19,669 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-02-15 12:28:19,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:28:19,717 INFO L263 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 19 conjunts are in the unsatisfiable core [2023-02-15 12:28:19,719 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:28:19,792 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-15 12:28:19,792 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:28:19,874 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-15 12:28:19,874 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:28:19,874 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [992286666] [2023-02-15 12:28:19,874 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:28:19,875 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [133144675] [2023-02-15 12:28:19,875 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [133144675] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:28:19,875 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:28:19,875 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6] total 11 [2023-02-15 12:28:19,875 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1187391449] [2023-02-15 12:28:19,875 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:28:19,876 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-02-15 12:28:19,876 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:28:19,877 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-02-15 12:28:19,877 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2023-02-15 12:28:19,877 INFO L87 Difference]: Start difference. First operand 22 states and 24 transitions. Second operand has 11 states, 11 states have (on average 1.9090909090909092) internal successors, (21), 10 states have internal predecessors, (21), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-02-15 12:28:20,050 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:28:20,050 INFO L93 Difference]: Finished difference Result 33 states and 37 transitions. [2023-02-15 12:28:20,050 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-02-15 12:28:20,051 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 1.9090909090909092) internal successors, (21), 10 states have internal predecessors, (21), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 16 [2023-02-15 12:28:20,051 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:28:20,051 INFO L225 Difference]: With dead ends: 33 [2023-02-15 12:28:20,051 INFO L226 Difference]: Without dead ends: 27 [2023-02-15 12:28:20,052 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=41, Invalid=115, Unknown=0, NotChecked=0, Total=156 [2023-02-15 12:28:20,052 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 20 mSDsluCounter, 26 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 39 SdHoareTripleChecker+Invalid, 67 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 12:28:20,053 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 39 Invalid, 67 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 12:28:20,053 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2023-02-15 12:28:20,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 23. [2023-02-15 12:28:20,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 17 states have (on average 1.0588235294117647) internal successors, (18), 17 states have internal predecessors, (18), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-02-15 12:28:20,057 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 23 transitions. [2023-02-15 12:28:20,057 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 23 transitions. Word has length 16 [2023-02-15 12:28:20,058 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:28:20,058 INFO L495 AbstractCegarLoop]: Abstraction has 23 states and 23 transitions. [2023-02-15 12:28:20,058 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 1.9090909090909092) internal successors, (21), 10 states have internal predecessors, (21), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-02-15 12:28:20,058 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 23 transitions. [2023-02-15 12:28:20,058 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-02-15 12:28:20,059 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:28:20,059 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:28:20,068 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-02-15 12:28:20,263 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:28:20,263 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:28:20,264 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:28:20,264 INFO L85 PathProgramCache]: Analyzing trace with hash -1711372296, now seen corresponding path program 1 times [2023-02-15 12:28:20,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:28:20,264 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1326179005] [2023-02-15 12:28:20,264 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:28:20,265 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:28:20,271 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:28:20,271 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1985602030] [2023-02-15 12:28:20,271 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:28:20,271 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:28:20,272 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:28:20,275 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) [2023-02-15 12:28:20,283 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-02-15 12:28:20,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:28:20,322 INFO L263 TraceCheckSpWp]: Trace formula consists of 75 conjuncts, 20 conjunts are in the unsatisfiable core [2023-02-15 12:28:20,323 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:28:20,428 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-02-15 12:28:20,429 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:28:58,225 WARN L859 $PredicateComparison]: unable to prove that (or (not (= |c___VERIFIER_assert_#in~cond| 0)) (forall ((|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_3| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| Int)) (or (= (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) (* |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_3| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|)) (= (mod (+ (* 3 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) (* 3 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) (* 2 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|)) 4) 0)))) is different from true [2023-02-15 12:29:16,283 WARN L859 $PredicateComparison]: unable to prove that (or (not (= |c___VERIFIER_assert_#in~cond| 0)) (forall ((|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_3| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| Int)) (or (= (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) (* |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_3| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|)) (= (mod (+ (* 3 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) (* 3 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) (* 2 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|)) 4) 0))) (= c___VERIFIER_assert_~cond 0)) is different from true [2023-02-15 12:29:22,324 WARN L837 $PredicateComparison]: unable to prove that (or (forall ((|ULTIMATE.start_main_~k~0#1| Int)) (or (not (< |c_ULTIMATE.start_main_~c~0#1| |ULTIMATE.start_main_~k~0#1|)) (< (+ |c_ULTIMATE.start_main_~c~0#1| 1) |ULTIMATE.start_main_~k~0#1|) (= (+ |ULTIMATE.start_main_~k~0#1| (* |c_ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~k~0#1|)) (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| 2) 1)))) (not (= (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 2) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3)) 4) 0))) is different from false [2023-02-15 12:29:24,342 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:29:24,343 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1326179005] [2023-02-15 12:29:24,343 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:29:24,343 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1985602030] [2023-02-15 12:29:24,343 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1985602030] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-15 12:29:24,343 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-15 12:29:24,343 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2023-02-15 12:29:24,343 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1661392641] [2023-02-15 12:29:24,343 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-15 12:29:24,343 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-02-15 12:29:24,343 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:29:24,344 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-02-15 12:29:24,344 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=121, Unknown=5, NotChecked=72, Total=240 [2023-02-15 12:29:24,344 INFO L87 Difference]: Start difference. First operand 23 states and 23 transitions. Second operand has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-02-15 12:29:24,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:29:24,418 INFO L93 Difference]: Finished difference Result 31 states and 32 transitions. [2023-02-15 12:29:24,419 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-02-15 12:29:24,419 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2023-02-15 12:29:24,419 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:29:24,420 INFO L225 Difference]: With dead ends: 31 [2023-02-15 12:29:24,420 INFO L226 Difference]: Without dead ends: 26 [2023-02-15 12:29:24,420 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 3 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 17.7s TimeCoverageRelationStatistics Valid=62, Invalid=185, Unknown=5, NotChecked=90, Total=342 [2023-02-15 12:29:24,421 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 6 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 91 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 60 SdHoareTripleChecker+Invalid, 91 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 91 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 12:29:24,421 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 60 Invalid, 91 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 91 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 12:29:24,422 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2023-02-15 12:29:24,425 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2023-02-15 12:29:24,425 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 19 states have (on average 1.0526315789473684) internal successors, (20), 19 states have internal predecessors, (20), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-02-15 12:29:24,425 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 27 transitions. [2023-02-15 12:29:24,425 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 27 transitions. Word has length 22 [2023-02-15 12:29:24,426 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:29:24,426 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 27 transitions. [2023-02-15 12:29:24,426 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-02-15 12:29:24,426 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 27 transitions. [2023-02-15 12:29:24,426 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2023-02-15 12:29:24,426 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:29:24,426 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:29:24,431 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-02-15 12:29:24,627 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:29:24,627 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:29:24,627 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:29:24,627 INFO L85 PathProgramCache]: Analyzing trace with hash -1075497887, now seen corresponding path program 2 times [2023-02-15 12:29:24,628 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:29:24,628 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [130609810] [2023-02-15 12:29:24,628 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:29:24,628 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:29:24,634 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:29:24,634 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1552227577] [2023-02-15 12:29:24,634 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-15 12:29:24,634 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:29:24,634 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:29:24,649 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) [2023-02-15 12:29:24,654 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-02-15 12:29:24,685 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-15 12:29:24,685 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:29:24,686 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 24 conjunts are in the unsatisfiable core [2023-02-15 12:29:24,687 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:29:24,780 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 8 proven. 13 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-02-15 12:29:24,780 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:29:31,024 WARN L837 $PredicateComparison]: unable to prove that (or (forall ((|ULTIMATE.start_main_~k~0#1| Int)) (or (not (< |c_ULTIMATE.start_main_~c~0#1| |ULTIMATE.start_main_~k~0#1|)) (< (+ |c_ULTIMATE.start_main_~c~0#1| 1) |ULTIMATE.start_main_~k~0#1|) (= (+ |ULTIMATE.start_main_~k~0#1| (* |c_ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~k~0#1|)) (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| 2) 1)))) (not (= (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 2) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3)) 4) 0))) is different from false [2023-02-15 12:29:31,026 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:29:31,026 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [130609810] [2023-02-15 12:29:31,026 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:29:31,026 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1552227577] [2023-02-15 12:29:31,026 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1552227577] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-15 12:29:31,026 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-15 12:29:31,026 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2023-02-15 12:29:31,026 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [847362299] [2023-02-15 12:29:31,027 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-15 12:29:31,027 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-02-15 12:29:31,027 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:29:31,027 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-02-15 12:29:31,027 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=148, Unknown=1, NotChecked=24, Total=210 [2023-02-15 12:29:31,028 INFO L87 Difference]: Start difference. First operand 26 states and 27 transitions. Second operand has 10 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-02-15 12:29:31,140 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:29:31,141 INFO L93 Difference]: Finished difference Result 34 states and 36 transitions. [2023-02-15 12:29:31,141 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-02-15 12:29:31,141 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 29 [2023-02-15 12:29:31,141 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:29:31,142 INFO L225 Difference]: With dead ends: 34 [2023-02-15 12:29:31,142 INFO L226 Difference]: Without dead ends: 29 [2023-02-15 12:29:31,142 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=56, Invalid=219, Unknown=1, NotChecked=30, Total=306 [2023-02-15 12:29:31,143 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 7 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 115 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 115 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 115 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 12:29:31,143 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 68 Invalid, 115 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 115 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 12:29:31,144 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2023-02-15 12:29:31,147 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2023-02-15 12:29:31,147 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 21 states have (on average 1.0476190476190477) internal successors, (22), 21 states have internal predecessors, (22), 5 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-02-15 12:29:31,148 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 31 transitions. [2023-02-15 12:29:31,148 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 31 transitions. Word has length 29 [2023-02-15 12:29:31,148 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:29:31,148 INFO L495 AbstractCegarLoop]: Abstraction has 29 states and 31 transitions. [2023-02-15 12:29:31,148 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-02-15 12:29:31,148 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 31 transitions. [2023-02-15 12:29:31,149 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2023-02-15 12:29:31,149 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:29:31,149 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:29:31,154 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-02-15 12:29:31,354 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:29:31,354 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:29:31,355 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:29:31,355 INFO L85 PathProgramCache]: Analyzing trace with hash 817917912, now seen corresponding path program 3 times [2023-02-15 12:29:31,355 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:29:31,355 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [199200223] [2023-02-15 12:29:31,355 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:29:31,356 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:29:31,361 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:29:31,362 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1292832669] [2023-02-15 12:29:31,362 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-15 12:29:31,362 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:29:31,362 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:29:31,367 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) [2023-02-15 12:29:31,375 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-02-15 12:29:31,412 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-02-15 12:29:31,412 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:29:31,413 INFO L263 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 28 conjunts are in the unsatisfiable core [2023-02-15 12:29:31,414 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:29:31,544 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 8 proven. 18 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-02-15 12:29:31,544 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:29:31,729 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 8 proven. 18 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-02-15 12:29:31,729 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:29:31,730 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [199200223] [2023-02-15 12:29:31,730 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:29:31,730 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1292832669] [2023-02-15 12:29:31,730 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1292832669] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:29:31,730 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:29:31,730 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 18 [2023-02-15 12:29:31,730 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [267226081] [2023-02-15 12:29:31,730 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:29:31,730 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-02-15 12:29:31,730 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:29:31,731 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-02-15 12:29:31,732 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=251, Unknown=0, NotChecked=0, Total=306 [2023-02-15 12:29:31,732 INFO L87 Difference]: Start difference. First operand 29 states and 31 transitions. Second operand has 18 states, 16 states have (on average 1.9375) internal successors, (31), 16 states have internal predecessors, (31), 10 states have call successors, (10), 3 states have call predecessors, (10), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2023-02-15 12:29:32,364 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:29:32,364 INFO L93 Difference]: Finished difference Result 47 states and 56 transitions. [2023-02-15 12:29:32,364 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2023-02-15 12:29:32,365 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 16 states have (on average 1.9375) internal successors, (31), 16 states have internal predecessors, (31), 10 states have call successors, (10), 3 states have call predecessors, (10), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Word has length 36 [2023-02-15 12:29:32,365 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:29:32,365 INFO L225 Difference]: With dead ends: 47 [2023-02-15 12:29:32,365 INFO L226 Difference]: Without dead ends: 41 [2023-02-15 12:29:32,366 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 55 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 127 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=187, Invalid=683, Unknown=0, NotChecked=0, Total=870 [2023-02-15 12:29:32,366 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 46 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 162 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 191 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 162 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 12:29:32,367 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 126 Invalid, 191 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 162 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 12:29:32,367 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2023-02-15 12:29:32,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2023-02-15 12:29:32,375 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 29 states have (on average 1.0344827586206897) internal successors, (30), 29 states have internal predecessors, (30), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2023-02-15 12:29:32,375 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 47 transitions. [2023-02-15 12:29:32,375 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 47 transitions. Word has length 36 [2023-02-15 12:29:32,376 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:29:32,376 INFO L495 AbstractCegarLoop]: Abstraction has 41 states and 47 transitions. [2023-02-15 12:29:32,376 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 16 states have (on average 1.9375) internal successors, (31), 16 states have internal predecessors, (31), 10 states have call successors, (10), 3 states have call predecessors, (10), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2023-02-15 12:29:32,376 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 47 transitions. [2023-02-15 12:29:32,381 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2023-02-15 12:29:32,381 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:29:32,381 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:29:32,386 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-02-15 12:29:32,586 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:29:32,586 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:29:32,586 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:29:32,586 INFO L85 PathProgramCache]: Analyzing trace with hash 385378200, now seen corresponding path program 4 times [2023-02-15 12:29:32,586 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:29:32,587 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [763074803] [2023-02-15 12:29:32,587 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:29:32,587 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:29:32,593 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:29:32,594 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [624936191] [2023-02-15 12:29:32,594 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-02-15 12:29:32,594 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:29:32,594 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:29:32,610 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) [2023-02-15 12:29:32,624 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-02-15 12:29:32,656 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-02-15 12:29:32,656 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:29:32,657 INFO L263 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 44 conjunts are in the unsatisfiable core [2023-02-15 12:29:32,659 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:29:32,818 INFO L134 CoverageAnalysis]: Checked inductivity of 212 backedges. 36 proven. 85 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-02-15 12:29:32,818 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:30:23,052 WARN L859 $PredicateComparison]: unable to prove that (or (not (= |c___VERIFIER_assert_#in~cond| 0)) (forall ((|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_18| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| Int)) (or (= (mod (+ (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| 3) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| 3) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| 2)) 4) 0) (= (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32|) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_18|))))) is different from true [2023-02-15 12:30:41,164 WARN L859 $PredicateComparison]: unable to prove that (or (not (= |c___VERIFIER_assert_#in~cond| 0)) (forall ((|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_18| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| Int)) (or (= (mod (+ (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| 3) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| 3) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| 2)) 4) 0) (= (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32|) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_32| |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_18|)))) (= c___VERIFIER_assert_~cond 0)) is different from true [2023-02-15 12:30:47,243 WARN L837 $PredicateComparison]: unable to prove that (or (forall ((|ULTIMATE.start_main_~k~0#1| Int)) (or (not (< |c_ULTIMATE.start_main_~c~0#1| |ULTIMATE.start_main_~k~0#1|)) (< (+ |c_ULTIMATE.start_main_~c~0#1| 1) |ULTIMATE.start_main_~k~0#1|) (= (+ |ULTIMATE.start_main_~k~0#1| (* |c_ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~k~0#1|)) (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| 2) 1)))) (not (= (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 2) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3)) 4) 0))) is different from false [2023-02-15 12:30:49,258 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:30:49,258 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [763074803] [2023-02-15 12:30:49,258 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:30:49,258 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [624936191] [2023-02-15 12:30:49,258 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [624936191] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-15 12:30:49,259 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-15 12:30:49,259 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2023-02-15 12:30:49,259 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1979902553] [2023-02-15 12:30:49,259 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-15 12:30:49,259 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-02-15 12:30:49,259 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:30:49,260 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-02-15 12:30:49,260 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=290, Unknown=10, NotChecked=108, Total=462 [2023-02-15 12:30:49,260 INFO L87 Difference]: Start difference. First operand 41 states and 47 transitions. Second operand has 15 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 14 states have internal predecessors, (29), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2023-02-15 12:30:49,509 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:30:49,509 INFO L93 Difference]: Finished difference Result 49 states and 56 transitions. [2023-02-15 12:30:49,509 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-02-15 12:30:49,509 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 14 states have internal predecessors, (29), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Word has length 64 [2023-02-15 12:30:49,510 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:30:49,510 INFO L225 Difference]: With dead ends: 49 [2023-02-15 12:30:49,510 INFO L226 Difference]: Without dead ends: 44 [2023-02-15 12:30:49,510 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 56 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 3 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 30.3s TimeCoverageRelationStatistics Valid=74, Invalid=390, Unknown=10, NotChecked=126, Total=600 [2023-02-15 12:30:49,511 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 6 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 409 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 409 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 409 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-02-15 12:30:49,511 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 186 Invalid, 409 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 409 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-02-15 12:30:49,512 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2023-02-15 12:30:49,519 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 44. [2023-02-15 12:30:49,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 31 states have (on average 1.032258064516129) internal successors, (32), 31 states have internal predecessors, (32), 10 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-02-15 12:30:49,520 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 51 transitions. [2023-02-15 12:30:49,520 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 51 transitions. Word has length 64 [2023-02-15 12:30:49,520 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:30:49,520 INFO L495 AbstractCegarLoop]: Abstraction has 44 states and 51 transitions. [2023-02-15 12:30:49,521 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 14 states have internal predecessors, (29), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2023-02-15 12:30:49,521 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 51 transitions. [2023-02-15 12:30:49,521 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2023-02-15 12:30:49,521 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:30:49,522 INFO L195 NwaCegarLoop]: trace histogram [10, 9, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:30:49,526 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-02-15 12:30:49,726 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:30:49,727 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:30:49,727 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:30:49,727 INFO L85 PathProgramCache]: Analyzing trace with hash 2073985217, now seen corresponding path program 5 times [2023-02-15 12:30:49,727 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:30:49,727 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [214875437] [2023-02-15 12:30:49,728 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:30:49,728 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:30:49,736 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:30:49,742 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1820758651] [2023-02-15 12:30:49,742 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2023-02-15 12:30:49,743 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:30:49,743 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:30:49,755 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:30:49,756 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-02-15 12:30:49,812 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2023-02-15 12:30:49,812 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:30:49,813 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 48 conjunts are in the unsatisfiable core [2023-02-15 12:30:49,815 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:30:50,017 INFO L134 CoverageAnalysis]: Checked inductivity of 270 backedges. 20 proven. 130 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2023-02-15 12:30:50,018 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:30:50,186 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:30:50,186 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [214875437] [2023-02-15 12:30:50,186 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:30:50,186 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1820758651] [2023-02-15 12:30:50,186 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1820758651] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-15 12:30:50,186 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-15 12:30:50,186 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2023-02-15 12:30:50,186 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [801891858] [2023-02-15 12:30:50,186 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-15 12:30:50,187 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-02-15 12:30:50,187 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:30:50,187 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-02-15 12:30:50,187 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=327, Unknown=0, NotChecked=0, Total=380 [2023-02-15 12:30:50,187 INFO L87 Difference]: Start difference. First operand 44 states and 51 transitions. Second operand has 16 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-02-15 12:30:50,420 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:30:50,420 INFO L93 Difference]: Finished difference Result 52 states and 60 transitions. [2023-02-15 12:30:50,420 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-02-15 12:30:50,420 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 71 [2023-02-15 12:30:50,420 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:30:50,421 INFO L225 Difference]: With dead ends: 52 [2023-02-15 12:30:50,421 INFO L226 Difference]: Without dead ends: 47 [2023-02-15 12:30:50,421 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=72, Invalid=434, Unknown=0, NotChecked=0, Total=506 [2023-02-15 12:30:50,422 INFO L413 NwaCegarLoop]: 26 mSDtfsCounter, 6 mSDsluCounter, 188 mSDsCounter, 0 mSdLazyCounter, 483 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 214 SdHoareTripleChecker+Invalid, 483 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 483 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-02-15 12:30:50,422 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 214 Invalid, 483 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 483 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-02-15 12:30:50,422 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-02-15 12:30:50,432 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2023-02-15 12:30:50,432 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 33 states have (on average 1.0303030303030303) internal successors, (34), 33 states have internal predecessors, (34), 11 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-02-15 12:30:50,433 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 55 transitions. [2023-02-15 12:30:50,433 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 55 transitions. Word has length 71 [2023-02-15 12:30:50,435 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:30:50,435 INFO L495 AbstractCegarLoop]: Abstraction has 47 states and 55 transitions. [2023-02-15 12:30:50,435 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-02-15 12:30:50,435 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 55 transitions. [2023-02-15 12:30:50,437 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2023-02-15 12:30:50,437 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:30:50,437 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:30:50,451 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-02-15 12:30:50,642 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-02-15 12:30:50,642 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:30:50,643 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:30:50,643 INFO L85 PathProgramCache]: Analyzing trace with hash 1353348984, now seen corresponding path program 6 times [2023-02-15 12:30:50,643 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:30:50,643 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [590514648] [2023-02-15 12:30:50,643 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:30:50,643 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:30:50,649 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:30:50,654 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1973920174] [2023-02-15 12:30:50,655 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2023-02-15 12:30:50,655 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:30:50,655 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:30:50,670 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:30:50,671 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-02-15 12:30:50,810 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) [2023-02-15 12:30:50,810 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:30:50,811 INFO L263 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 53 conjunts are in the unsatisfiable core [2023-02-15 12:30:50,813 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:30:51,122 INFO L134 CoverageAnalysis]: Checked inductivity of 335 backedges. 20 proven. 135 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2023-02-15 12:30:51,122 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:30:51,639 INFO L134 CoverageAnalysis]: Checked inductivity of 335 backedges. 20 proven. 135 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2023-02-15 12:30:51,639 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:30:51,639 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [590514648] [2023-02-15 12:30:51,639 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:30:51,639 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1973920174] [2023-02-15 12:30:51,639 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1973920174] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:30:51,639 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:30:51,639 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 15] total 30 [2023-02-15 12:30:51,639 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [164991654] [2023-02-15 12:30:51,639 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:30:51,640 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2023-02-15 12:30:51,640 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:30:51,640 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2023-02-15 12:30:51,641 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=158, Invalid=712, Unknown=0, NotChecked=0, Total=870 [2023-02-15 12:30:51,641 INFO L87 Difference]: Start difference. First operand 47 states and 55 transitions. Second operand has 30 states, 28 states have (on average 1.9642857142857142) internal successors, (55), 28 states have internal predecessors, (55), 22 states have call successors, (22), 3 states have call predecessors, (22), 1 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2023-02-15 12:30:54,363 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:30:54,363 INFO L93 Difference]: Finished difference Result 83 states and 110 transitions. [2023-02-15 12:30:54,364 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2023-02-15 12:30:54,364 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 28 states have (on average 1.9642857142857142) internal successors, (55), 28 states have internal predecessors, (55), 22 states have call successors, (22), 3 states have call predecessors, (22), 1 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) Word has length 78 [2023-02-15 12:30:54,364 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:30:54,365 INFO L225 Difference]: With dead ends: 83 [2023-02-15 12:30:54,365 INFO L226 Difference]: Without dead ends: 77 [2023-02-15 12:30:54,366 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 179 GetRequests, 127 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 487 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=626, Invalid=2236, Unknown=0, NotChecked=0, Total=2862 [2023-02-15 12:30:54,366 INFO L413 NwaCegarLoop]: 49 mSDtfsCounter, 133 mSDsluCounter, 303 mSDsCounter, 0 mSdLazyCounter, 621 mSolverCounterSat, 98 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 133 SdHoareTripleChecker+Valid, 352 SdHoareTripleChecker+Invalid, 719 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 98 IncrementalHoareTripleChecker+Valid, 621 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-02-15 12:30:54,366 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [133 Valid, 352 Invalid, 719 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [98 Valid, 621 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-02-15 12:30:54,366 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2023-02-15 12:30:54,393 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2023-02-15 12:30:54,393 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 53 states have (on average 1.0188679245283019) internal successors, (54), 53 states have internal predecessors, (54), 21 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2023-02-15 12:30:54,396 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 95 transitions. [2023-02-15 12:30:54,396 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 95 transitions. Word has length 78 [2023-02-15 12:30:54,396 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:30:54,396 INFO L495 AbstractCegarLoop]: Abstraction has 77 states and 95 transitions. [2023-02-15 12:30:54,396 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 28 states have (on average 1.9642857142857142) internal successors, (55), 28 states have internal predecessors, (55), 22 states have call successors, (22), 3 states have call predecessors, (22), 1 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2023-02-15 12:30:54,396 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 95 transitions. [2023-02-15 12:30:54,401 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 149 [2023-02-15 12:30:54,402 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:30:54,402 INFO L195 NwaCegarLoop]: trace histogram [21, 20, 20, 20, 20, 20, 19, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:30:54,409 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-02-15 12:30:54,605 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:30:54,605 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:30:54,605 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:30:54,605 INFO L85 PathProgramCache]: Analyzing trace with hash 2058456792, now seen corresponding path program 7 times [2023-02-15 12:30:54,605 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:30:54,605 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [130954730] [2023-02-15 12:30:54,605 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:30:54,605 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:30:54,613 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:30:54,613 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1856393432] [2023-02-15 12:30:54,613 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-02-15 12:30:54,613 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:30:54,613 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:30:54,614 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:30:54,616 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-02-15 12:30:54,870 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:30:54,873 INFO L263 TraceCheckSpWp]: Trace formula consists of 381 conjuncts, 92 conjunts are in the unsatisfiable core [2023-02-15 12:30:54,876 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:30:55,530 INFO L134 CoverageAnalysis]: Checked inductivity of 1370 backedges. 40 proven. 570 refuted. 0 times theorem prover too weak. 760 trivial. 0 not checked. [2023-02-15 12:30:55,531 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:30:56,701 INFO L134 CoverageAnalysis]: Checked inductivity of 1370 backedges. 40 proven. 570 refuted. 0 times theorem prover too weak. 760 trivial. 0 not checked. [2023-02-15 12:30:56,702 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:30:56,702 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [130954730] [2023-02-15 12:30:56,702 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:30:56,702 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1856393432] [2023-02-15 12:30:56,702 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1856393432] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:30:56,702 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:30:56,702 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 25] total 50 [2023-02-15 12:30:56,702 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [852131302] [2023-02-15 12:30:56,702 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:30:56,703 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2023-02-15 12:30:56,703 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:30:56,703 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2023-02-15 12:30:56,704 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=487, Invalid=1963, Unknown=0, NotChecked=0, Total=2450 [2023-02-15 12:30:56,704 INFO L87 Difference]: Start difference. First operand 77 states and 95 transitions. Second operand has 50 states, 48 states have (on average 1.9791666666666667) internal successors, (95), 48 states have internal predecessors, (95), 42 states have call successors, (42), 3 states have call predecessors, (42), 1 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2023-02-15 12:31:05,918 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:31:05,919 INFO L93 Difference]: Finished difference Result 143 states and 200 transitions. [2023-02-15 12:31:05,919 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 49 states. [2023-02-15 12:31:05,919 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 48 states have (on average 1.9791666666666667) internal successors, (95), 48 states have internal predecessors, (95), 42 states have call successors, (42), 3 states have call predecessors, (42), 1 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) Word has length 148 [2023-02-15 12:31:05,920 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:31:05,922 INFO L225 Difference]: With dead ends: 143 [2023-02-15 12:31:05,922 INFO L226 Difference]: Without dead ends: 137 [2023-02-15 12:31:05,923 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 339 GetRequests, 247 SyntacticMatches, 0 SemanticMatches, 92 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1567 ImplicationChecksByTransitivity, 8.8s TimeCoverageRelationStatistics Valid=1995, Invalid=6747, Unknown=0, NotChecked=0, Total=8742 [2023-02-15 12:31:05,924 INFO L413 NwaCegarLoop]: 89 mSDtfsCounter, 357 mSDsluCounter, 846 mSDsCounter, 0 mSdLazyCounter, 2020 mSolverCounterSat, 293 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 357 SdHoareTripleChecker+Valid, 935 SdHoareTripleChecker+Invalid, 2313 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 293 IncrementalHoareTripleChecker+Valid, 2020 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2023-02-15 12:31:05,924 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [357 Valid, 935 Invalid, 2313 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [293 Valid, 2020 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2023-02-15 12:31:05,925 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2023-02-15 12:31:05,972 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 137. [2023-02-15 12:31:05,973 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 137 states, 93 states have (on average 1.010752688172043) internal successors, (94), 93 states have internal predecessors, (94), 41 states have call successors, (41), 3 states have call predecessors, (41), 2 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2023-02-15 12:31:05,973 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 175 transitions. [2023-02-15 12:31:05,974 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 175 transitions. Word has length 148 [2023-02-15 12:31:05,974 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:31:05,974 INFO L495 AbstractCegarLoop]: Abstraction has 137 states and 175 transitions. [2023-02-15 12:31:05,974 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 50 states, 48 states have (on average 1.9791666666666667) internal successors, (95), 48 states have internal predecessors, (95), 42 states have call successors, (42), 3 states have call predecessors, (42), 1 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2023-02-15 12:31:05,974 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 175 transitions. [2023-02-15 12:31:05,976 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 289 [2023-02-15 12:31:05,977 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:31:05,977 INFO L195 NwaCegarLoop]: trace histogram [41, 40, 40, 40, 40, 40, 39, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:31:05,985 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-02-15 12:31:06,185 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-02-15 12:31:06,185 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:31:06,186 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:31:06,186 INFO L85 PathProgramCache]: Analyzing trace with hash 1734321560, now seen corresponding path program 8 times [2023-02-15 12:31:06,186 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:31:06,186 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [456278110] [2023-02-15 12:31:06,186 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:31:06,186 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:31:06,197 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:31:06,197 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1022865082] [2023-02-15 12:31:06,197 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-15 12:31:06,197 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:31:06,197 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:31:06,198 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:31:06,200 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-02-15 12:31:06,306 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-15 12:31:06,306 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:31:06,308 INFO L263 TraceCheckSpWp]: Trace formula consists of 721 conjuncts, 45 conjunts are in the unsatisfiable core [2023-02-15 12:31:06,313 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:31:07,350 INFO L134 CoverageAnalysis]: Checked inductivity of 5540 backedges. 2574 proven. 0 refuted. 0 times theorem prover too weak. 2966 trivial. 0 not checked. [2023-02-15 12:31:07,350 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 12:31:07,350 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:31:07,350 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [456278110] [2023-02-15 12:31:07,350 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:31:07,350 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1022865082] [2023-02-15 12:31:07,351 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1022865082] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 12:31:07,351 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 12:31:07,351 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [43] imperfect sequences [] total 43 [2023-02-15 12:31:07,351 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [115617679] [2023-02-15 12:31:07,351 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 12:31:07,351 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 43 states [2023-02-15 12:31:07,351 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:31:07,352 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2023-02-15 12:31:07,352 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=863, Invalid=943, Unknown=0, NotChecked=0, Total=1806 [2023-02-15 12:31:07,353 INFO L87 Difference]: Start difference. First operand 137 states and 175 transitions. Second operand has 43 states, 43 states have (on average 2.13953488372093) internal successors, (92), 43 states have internal predecessors, (92), 40 states have call successors, (41), 2 states have call predecessors, (41), 2 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2023-02-15 12:31:07,910 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:31:07,911 INFO L93 Difference]: Finished difference Result 141 states and 178 transitions. [2023-02-15 12:31:07,911 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2023-02-15 12:31:07,911 INFO L78 Accepts]: Start accepts. Automaton has has 43 states, 43 states have (on average 2.13953488372093) internal successors, (92), 43 states have internal predecessors, (92), 40 states have call successors, (41), 2 states have call predecessors, (41), 2 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) Word has length 288 [2023-02-15 12:31:07,913 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:31:07,913 INFO L225 Difference]: With dead ends: 141 [2023-02-15 12:31:07,913 INFO L226 Difference]: Without dead ends: 0 [2023-02-15 12:31:07,917 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 309 GetRequests, 246 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 605 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=1413, Invalid=2747, Unknown=0, NotChecked=0, Total=4160 [2023-02-15 12:31:07,919 INFO L413 NwaCegarLoop]: 69 mSDtfsCounter, 4 mSDsluCounter, 203 mSDsCounter, 0 mSdLazyCounter, 184 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 272 SdHoareTripleChecker+Invalid, 227 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 184 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 12:31:07,919 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 272 Invalid, 227 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 184 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 12:31:07,919 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2023-02-15 12:31:07,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2023-02-15 12:31:07,919 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-02-15 12:31:07,919 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2023-02-15 12:31:07,920 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 288 [2023-02-15 12:31:07,920 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:31:07,920 INFO L495 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2023-02-15 12:31:07,920 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 43 states, 43 states have (on average 2.13953488372093) internal successors, (92), 43 states have internal predecessors, (92), 40 states have call successors, (41), 2 states have call predecessors, (41), 2 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2023-02-15 12:31:07,920 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2023-02-15 12:31:07,920 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2023-02-15 12:31:07,924 INFO L805 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-02-15 12:31:07,932 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-02-15 12:31:08,130 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-02-15 12:31:08,132 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2023-02-15 12:31:10,568 INFO L899 garLoopResultBuilder]: For program point ULTIMATE.startEXIT(line -1) no Hoare annotation was computed. [2023-02-15 12:31:10,569 INFO L895 garLoopResultBuilder]: At program point L27-2(lines 27 36) the Hoare annotation is: (let ((.cse5 (* |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1|))) (let ((.cse4 (<= 0 |ULTIMATE.start_main_~k~0#1|)) (.cse0 (= |ULTIMATE.start_assume_abort_if_not_~cond#1| 1)) (.cse1 (or (= (* |ULTIMATE.start_main_~k~0#1| |ULTIMATE.start_main_~y~0#1|) .cse5) (< |ULTIMATE.start_main_~c~0#1| |ULTIMATE.start_main_~k~0#1|))) (.cse2 (= (+ (* (* |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1|) 2) (* |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1|) .cse5) (* |ULTIMATE.start_main_~x~0#1| 4))) (.cse3 (<= |ULTIMATE.start_main_~k~0#1| 20))) (or (and .cse0 (<= 9 |ULTIMATE.start_main_~c~0#1|) .cse1 (<= |ULTIMATE.start_main_~c~0#1| 9) (= 9 |ULTIMATE.start_main_~y~0#1|) .cse2 .cse3) (and .cse0 (= |ULTIMATE.start_main_~c~0#1| 18) (= |ULTIMATE.start_main_~y~0#1| 18) .cse1 .cse2 .cse3) (and .cse0 (= |ULTIMATE.start_main_~c~0#1| 10) (= |ULTIMATE.start_main_~y~0#1| 10) .cse1 .cse2 .cse3) (and .cse0 (= 5 |ULTIMATE.start_main_~y~0#1|) (= 5 |ULTIMATE.start_main_~c~0#1|) .cse1 .cse2 .cse3) (and .cse0 (= |ULTIMATE.start_main_~c~0#1| 8) (= |ULTIMATE.start_main_~y~0#1| 8) (< 7 |ULTIMATE.start_main_~k~0#1|) .cse2 .cse3) (and .cse4 .cse0 (<= 20 |ULTIMATE.start_main_~c~0#1|) .cse1 .cse2 .cse3) (and .cse0 (<= 19 |ULTIMATE.start_main_~c~0#1|) (<= |ULTIMATE.start_main_~c~0#1| 19) (= 19 |ULTIMATE.start_main_~y~0#1|) .cse2 (< 18 |ULTIMATE.start_main_~k~0#1|) .cse3) (and .cse0 (= |ULTIMATE.start_main_~c~0#1| 11) (= |ULTIMATE.start_main_~y~0#1| 11) .cse1 .cse2 .cse3) (and .cse0 .cse1 .cse2 (= |ULTIMATE.start_main_~y~0#1| 15) (= |ULTIMATE.start_main_~c~0#1| 15) .cse3) (and .cse0 (<= |ULTIMATE.start_main_~c~0#1| 1) (<= 1 |ULTIMATE.start_main_~c~0#1|) (= |ULTIMATE.start_main_~y~0#1| 1) .cse1 .cse2 .cse3) (and .cse0 (= 7 |ULTIMATE.start_main_~y~0#1|) (<= 7 |ULTIMATE.start_main_~c~0#1|) (< 6 |ULTIMATE.start_main_~k~0#1|) (<= |ULTIMATE.start_main_~c~0#1| 7) .cse2 .cse3) (and .cse0 (= |ULTIMATE.start_main_~y~0#1| 17) .cse1 (= |ULTIMATE.start_main_~c~0#1| 17) .cse2 .cse3) (and .cse0 (= 2 |ULTIMATE.start_main_~y~0#1|) .cse1 (= 2 |ULTIMATE.start_main_~c~0#1|) .cse2 .cse3) (and .cse0 (= 6 |ULTIMATE.start_main_~y~0#1|) .cse1 .cse2 (= 6 |ULTIMATE.start_main_~c~0#1|) .cse3) (and .cse0 (= |ULTIMATE.start_main_~y~0#1| 4) .cse1 (= |ULTIMATE.start_main_~c~0#1| 4) .cse2 .cse3) (and .cse0 (= 14 |ULTIMATE.start_main_~y~0#1|) .cse1 (= 14 |ULTIMATE.start_main_~c~0#1|) .cse2 .cse3) (and .cse4 .cse0 (= |ULTIMATE.start_main_~c~0#1| 0) (= |ULTIMATE.start_main_~y~0#1| 0) (= |ULTIMATE.start_main_~x~0#1| 0) .cse3) (and .cse0 (= |ULTIMATE.start_main_~y~0#1| 12) .cse1 (= |ULTIMATE.start_main_~c~0#1| 12) .cse2 .cse3) (and .cse0 (= 3 |ULTIMATE.start_main_~y~0#1|) (= 3 |ULTIMATE.start_main_~c~0#1|) .cse1 .cse2 .cse3) (and .cse0 .cse1 (= |ULTIMATE.start_main_~c~0#1| 13) .cse2 (= |ULTIMATE.start_main_~y~0#1| 13) .cse3) (and .cse0 (= 16 |ULTIMATE.start_main_~y~0#1|) (= 16 |ULTIMATE.start_main_~c~0#1|) .cse1 .cse2 .cse3)))) [2023-02-15 12:31:10,569 INFO L895 garLoopResultBuilder]: At program point L27-3(lines 27 36) the Hoare annotation is: (let ((.cse1 (* |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1|))) (let ((.cse0 (= (+ (* (* |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1|) 2) (* |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1|) .cse1) (* |ULTIMATE.start_main_~x~0#1| 4)))) (or (and (<= |ULTIMATE.start_main_~k~0#1| 1) (<= |ULTIMATE.start_main_~c~0#1| 1) (= |ULTIMATE.start_main_~y~0#1| 1) (< 0 |ULTIMATE.start_main_~k~0#1|) .cse0) (let ((.cse3 (< (+ |ULTIMATE.start_main_~c~0#1| 1) |ULTIMATE.start_main_~k~0#1|)) (.cse2 (< (+ 2 |ULTIMATE.start_main_~c~0#1|) |ULTIMATE.start_main_~k~0#1|))) (and (<= 0 |ULTIMATE.start_main_~k~0#1|) (= |ULTIMATE.start_assume_abort_if_not_~cond#1| 1) (= (* |ULTIMATE.start_main_~k~0#1| |ULTIMATE.start_main_~y~0#1|) .cse1) (or .cse2 (not .cse3)) (or (not (< |ULTIMATE.start_main_~c~0#1| |ULTIMATE.start_main_~k~0#1|)) .cse3) (or (< (+ 3 |ULTIMATE.start_main_~c~0#1|) |ULTIMATE.start_main_~k~0#1|) (not .cse2)) .cse0 (<= |ULTIMATE.start_main_~k~0#1| 20))) (and (<= |ULTIMATE.start_main_~k~0#1| 2) (= 2 |ULTIMATE.start_main_~y~0#1|) (< 1 |ULTIMATE.start_main_~k~0#1|) (<= |ULTIMATE.start_main_~c~0#1| 2) .cse0) (and (= |ULTIMATE.start_main_~y~0#1| 0) (= |ULTIMATE.start_main_~x~0#1| 0))))) [2023-02-15 12:31:10,569 INFO L899 garLoopResultBuilder]: For program point $Ultimate##0(line -1) no Hoare annotation was computed. [2023-02-15 12:31:10,569 INFO L902 garLoopResultBuilder]: At program point main_returnLabel#1(lines 17 40) the Hoare annotation is: true [2023-02-15 12:31:10,569 INFO L899 garLoopResultBuilder]: For program point L7(line 7) no Hoare annotation was computed. [2023-02-15 12:31:10,569 INFO L899 garLoopResultBuilder]: For program point L38(line 38) no Hoare annotation was computed. [2023-02-15 12:31:10,569 INFO L899 garLoopResultBuilder]: For program point L-1(line -1) no Hoare annotation was computed. [2023-02-15 12:31:10,569 INFO L899 garLoopResultBuilder]: For program point ULTIMATE.startFINAL(line -1) no Hoare annotation was computed. [2023-02-15 12:31:10,569 INFO L895 garLoopResultBuilder]: At program point L28(line 28) the Hoare annotation is: (let ((.cse5 (* |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1|))) (let ((.cse4 (<= 0 |ULTIMATE.start_main_~k~0#1|)) (.cse0 (= |ULTIMATE.start_assume_abort_if_not_~cond#1| 1)) (.cse1 (or (= (* |ULTIMATE.start_main_~k~0#1| |ULTIMATE.start_main_~y~0#1|) .cse5) (< |ULTIMATE.start_main_~c~0#1| |ULTIMATE.start_main_~k~0#1|))) (.cse2 (= (+ (* (* |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1|) 2) (* |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1|) .cse5) (* |ULTIMATE.start_main_~x~0#1| 4))) (.cse3 (<= |ULTIMATE.start_main_~k~0#1| 20))) (or (and .cse0 (<= 9 |ULTIMATE.start_main_~c~0#1|) .cse1 (<= |ULTIMATE.start_main_~c~0#1| 9) (= 9 |ULTIMATE.start_main_~y~0#1|) .cse2 .cse3) (and .cse0 (= |ULTIMATE.start_main_~c~0#1| 18) (= |ULTIMATE.start_main_~y~0#1| 18) .cse1 .cse2 .cse3) (and .cse0 (= |ULTIMATE.start_main_~c~0#1| 10) (= |ULTIMATE.start_main_~y~0#1| 10) .cse1 .cse2 .cse3) (and .cse0 (= 5 |ULTIMATE.start_main_~y~0#1|) (= 5 |ULTIMATE.start_main_~c~0#1|) .cse1 .cse2 .cse3) (and .cse0 (= |ULTIMATE.start_main_~c~0#1| 8) (= |ULTIMATE.start_main_~y~0#1| 8) (< 7 |ULTIMATE.start_main_~k~0#1|) .cse2 .cse3) (and .cse4 .cse0 (<= 20 |ULTIMATE.start_main_~c~0#1|) .cse1 .cse2 .cse3) (and .cse0 (<= 19 |ULTIMATE.start_main_~c~0#1|) (<= |ULTIMATE.start_main_~c~0#1| 19) (= 19 |ULTIMATE.start_main_~y~0#1|) .cse2 (< 18 |ULTIMATE.start_main_~k~0#1|) .cse3) (and .cse0 (= |ULTIMATE.start_main_~c~0#1| 11) (= |ULTIMATE.start_main_~y~0#1| 11) .cse1 .cse2 .cse3) (and .cse0 .cse1 .cse2 (= |ULTIMATE.start_main_~y~0#1| 15) (= |ULTIMATE.start_main_~c~0#1| 15) .cse3) (and .cse0 (<= |ULTIMATE.start_main_~c~0#1| 1) (<= 1 |ULTIMATE.start_main_~c~0#1|) (= |ULTIMATE.start_main_~y~0#1| 1) .cse1 .cse2 .cse3) (and .cse0 (= 7 |ULTIMATE.start_main_~y~0#1|) (<= 7 |ULTIMATE.start_main_~c~0#1|) (< 6 |ULTIMATE.start_main_~k~0#1|) (<= |ULTIMATE.start_main_~c~0#1| 7) .cse2 .cse3) (and .cse0 (= |ULTIMATE.start_main_~y~0#1| 17) .cse1 (= |ULTIMATE.start_main_~c~0#1| 17) .cse2 .cse3) (and .cse0 (= 2 |ULTIMATE.start_main_~y~0#1|) .cse1 (= 2 |ULTIMATE.start_main_~c~0#1|) .cse2 .cse3) (and .cse0 (= 6 |ULTIMATE.start_main_~y~0#1|) .cse1 .cse2 (= 6 |ULTIMATE.start_main_~c~0#1|) .cse3) (and .cse0 (= |ULTIMATE.start_main_~y~0#1| 4) .cse1 (= |ULTIMATE.start_main_~c~0#1| 4) .cse2 .cse3) (and .cse0 (= 14 |ULTIMATE.start_main_~y~0#1|) .cse1 (= 14 |ULTIMATE.start_main_~c~0#1|) .cse2 .cse3) (and .cse4 .cse0 (= |ULTIMATE.start_main_~c~0#1| 0) (= |ULTIMATE.start_main_~y~0#1| 0) (= |ULTIMATE.start_main_~x~0#1| 0) .cse3) (and .cse0 (= |ULTIMATE.start_main_~y~0#1| 12) .cse1 (= |ULTIMATE.start_main_~c~0#1| 12) .cse2 .cse3) (and .cse0 (= 3 |ULTIMATE.start_main_~y~0#1|) (= 3 |ULTIMATE.start_main_~c~0#1|) .cse1 .cse2 .cse3) (and .cse0 .cse1 (= |ULTIMATE.start_main_~c~0#1| 13) .cse2 (= |ULTIMATE.start_main_~y~0#1| 13) .cse3) (and .cse0 (= 16 |ULTIMATE.start_main_~y~0#1|) (= 16 |ULTIMATE.start_main_~c~0#1|) .cse1 .cse2 .cse3)))) [2023-02-15 12:31:10,569 INFO L899 garLoopResultBuilder]: For program point L28-1(lines 27 36) no Hoare annotation was computed. [2023-02-15 12:31:10,569 INFO L899 garLoopResultBuilder]: For program point L6(lines 6 8) no Hoare annotation was computed. [2023-02-15 12:31:10,569 INFO L895 garLoopResultBuilder]: At program point L37(line 37) the Hoare annotation is: (= (+ (* (* |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1|) 2) (* |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1|) (* |ULTIMATE.start_main_~y~0#1| |ULTIMATE.start_main_~y~0#1|)) (* |ULTIMATE.start_main_~x~0#1| 4)) [2023-02-15 12:31:10,569 INFO L899 garLoopResultBuilder]: For program point L11(lines 11 12) no Hoare annotation was computed. [2023-02-15 12:31:10,570 INFO L899 garLoopResultBuilder]: For program point L10(lines 10 13) no Hoare annotation was computed. [2023-02-15 12:31:10,570 INFO L899 garLoopResultBuilder]: For program point __VERIFIER_assertEXIT(lines 9 15) no Hoare annotation was computed. [2023-02-15 12:31:10,570 INFO L902 garLoopResultBuilder]: At program point $Ultimate##0(lines 9 15) the Hoare annotation is: true [2023-02-15 12:31:10,570 INFO L899 garLoopResultBuilder]: For program point L10-2(lines 9 15) no Hoare annotation was computed. [2023-02-15 12:31:10,570 INFO L899 garLoopResultBuilder]: For program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 12) no Hoare annotation was computed. [2023-02-15 12:31:10,572 INFO L445 BasicCegarLoop]: Path program histogram: [8, 1, 1, 1] [2023-02-15 12:31:10,573 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2023-02-15 12:31:10,609 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 15.02 12:31:10 BoogieIcfgContainer [2023-02-15 12:31:10,610 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-02-15 12:31:10,616 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2023-02-15 12:31:10,617 INFO L271 PluginConnector]: Initializing Witness Printer... [2023-02-15 12:31:10,617 INFO L275 PluginConnector]: Witness Printer initialized [2023-02-15 12:31:10,617 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.02 12:28:18" (3/4) ... [2023-02-15 12:31:10,619 INFO L137 WitnessPrinter]: Generating witness for correct program [2023-02-15 12:31:10,623 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2023-02-15 12:31:10,625 INFO L961 BoogieBacktranslator]: Reduced CFG by removing 12 nodes and edges [2023-02-15 12:31:10,625 INFO L961 BoogieBacktranslator]: Reduced CFG by removing 5 nodes and edges [2023-02-15 12:31:10,626 INFO L961 BoogieBacktranslator]: Reduced CFG by removing 2 nodes and edges [2023-02-15 12:31:10,626 INFO L961 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2023-02-15 12:31:10,648 INFO L141 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2023-02-15 12:31:10,648 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2023-02-15 12:31:10,649 INFO L158 Benchmark]: Toolchain (without parser) took 172294.46ms. Allocated memory is still 130.0MB. Free memory was 86.9MB in the beginning and 43.6MB in the end (delta: 43.3MB). Peak memory consumption was 44.8MB. Max. memory is 16.1GB. [2023-02-15 12:31:10,649 INFO L158 Benchmark]: CDTParser took 0.08ms. Allocated memory is still 102.8MB. Free memory is still 74.2MB. There was no memory consumed. Max. memory is 16.1GB. [2023-02-15 12:31:10,649 INFO L158 Benchmark]: CACSL2BoogieTranslator took 177.22ms. Allocated memory is still 130.0MB. Free memory was 86.9MB in the beginning and 76.4MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2023-02-15 12:31:10,649 INFO L158 Benchmark]: Boogie Procedure Inliner took 20.36ms. Allocated memory is still 130.0MB. Free memory was 76.4MB in the beginning and 74.8MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2023-02-15 12:31:10,650 INFO L158 Benchmark]: Boogie Preprocessor took 11.43ms. Allocated memory is still 130.0MB. Free memory was 74.8MB in the beginning and 73.8MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2023-02-15 12:31:10,650 INFO L158 Benchmark]: RCFGBuilder took 167.54ms. Allocated memory is still 130.0MB. Free memory was 73.8MB in the beginning and 63.9MB in the end (delta: 9.9MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2023-02-15 12:31:10,650 INFO L158 Benchmark]: TraceAbstraction took 171881.12ms. Allocated memory is still 130.0MB. Free memory was 63.4MB in the beginning and 46.8MB in the end (delta: 16.6MB). Peak memory consumption was 42.8MB. Max. memory is 16.1GB. [2023-02-15 12:31:10,650 INFO L158 Benchmark]: Witness Printer took 32.01ms. Allocated memory is still 130.0MB. Free memory was 46.8MB in the beginning and 43.6MB in the end (delta: 3.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2023-02-15 12:31:10,652 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.08ms. Allocated memory is still 102.8MB. Free memory is still 74.2MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 177.22ms. Allocated memory is still 130.0MB. Free memory was 86.9MB in the beginning and 76.4MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 20.36ms. Allocated memory is still 130.0MB. Free memory was 76.4MB in the beginning and 74.8MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 11.43ms. Allocated memory is still 130.0MB. Free memory was 74.8MB in the beginning and 73.8MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 167.54ms. Allocated memory is still 130.0MB. Free memory was 73.8MB in the beginning and 63.9MB in the end (delta: 9.9MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * TraceAbstraction took 171881.12ms. Allocated memory is still 130.0MB. Free memory was 63.4MB in the beginning and 46.8MB in the end (delta: 16.6MB). Peak memory consumption was 42.8MB. Max. memory is 16.1GB. * Witness Printer took 32.01ms. Allocated memory is still 130.0MB. Free memory was 46.8MB in the beginning and 43.6MB in the end (delta: 3.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 12]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 19 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 171.8s, OverallIterations: 11, TraceHistogramMax: 41, PathProgramHistogramMax: 8, EmptinessCheckTime: 0.0s, AutomataDifference: 14.1s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 2.4s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 596 SdHoareTripleChecker+Valid, 2.8s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 591 mSDsluCounter, 2318 SdHoareTripleChecker+Invalid, 2.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1962 mSDsCounter, 475 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 4170 IncrementalHoareTripleChecker+Invalid, 4645 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 475 mSolverCounterUnsat, 356 mSDtfsCounter, 4170 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1205 GetRequests, 878 SyntacticMatches, 0 SemanticMatches, 327 ConstructedPredicates, 7 IntricatePredicates, 0 DeprecatedPredicates, 2844 ImplicationChecksByTransitivity, 63.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=137occurred in iteration=10, InterpolantAutomatonStates: 186, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 11 MinimizatonAttempts, 4 StatesRemovedByMinimization, 1 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 6 LocationsWithAnnotation, 63 PreInvPairs, 120 NumberOfFragments, 1899 HoareAnnotationTreeSize, 63 FomulaSimplifications, 0 FormulaSimplificationTreeSizeReduction, 0.0s HoareSimplificationTime, 6 FomulaSimplificationsInter, 7079 FormulaSimplificationTreeSizeReductionInter, 2.4s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 151.6s InterpolantComputationTime, 779 NumberOfCodeBlocks, 777 NumberOfCodeBlocksAsserted, 34 NumberOfCheckSat, 1033 ConstructedInterpolants, 0 QuantifiedInterpolants, 6725 SizeOfPredicates, 43 NumberOfNonLiveVariables, 2092 ConjunctsInSsa, 384 ConjunctsInUnsatCore, 15 InterpolantComputations, 3 PerfectInterpolantSequences, 7896/9578 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 17]: Loop Invariant Derived loop invariant: 1 - InvariantResult [Line: 27]: Loop Invariant Derived loop invariant: (((((((((((((((((((((((((cond == 1 && 9 <= c) && (k * y == y * y || c < k)) && c <= 9) && 9 == y) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20) || (((((cond == 1 && c == 18) && y == 18) && (k * y == y * y || c < k)) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || (((((cond == 1 && c == 10) && y == 10) && (k * y == y * y || c < k)) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || (((((cond == 1 && 5 == y) && 5 == c) && (k * y == y * y || c < k)) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || (((((cond == 1 && c == 8) && y == 8) && 7 < k) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || (((((0 <= k && cond == 1) && 20 <= c) && (k * y == y * y || c < k)) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || ((((((cond == 1 && 19 <= c) && c <= 19) && 19 == y) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && 18 < k) && k <= 20)) || (((((cond == 1 && c == 11) && y == 11) && (k * y == y * y || c < k)) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || (((((cond == 1 && (k * y == y * y || c < k)) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && y == 15) && c == 15) && k <= 20)) || ((((((cond == 1 && c <= 1) && 1 <= c) && y == 1) && (k * y == y * y || c < k)) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || ((((((cond == 1 && 7 == y) && 7 <= c) && 6 < k) && c <= 7) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || (((((cond == 1 && y == 17) && (k * y == y * y || c < k)) && c == 17) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || (((((cond == 1 && 2 == y) && (k * y == y * y || c < k)) && 2 == c) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || (((((cond == 1 && 6 == y) && (k * y == y * y || c < k)) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && 6 == c) && k <= 20)) || (((((cond == 1 && y == 4) && (k * y == y * y || c < k)) && c == 4) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || (((((cond == 1 && 14 == y) && (k * y == y * y || c < k)) && 14 == c) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || (((((0 <= k && cond == 1) && c == 0) && y == 0) && x == 0) && k <= 20)) || (((((cond == 1 && y == 12) && (k * y == y * y || c < k)) && c == 12) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || (((((cond == 1 && 3 == y) && 3 == c) && (k * y == y * y || c < k)) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20)) || (((((cond == 1 && (k * y == y * y || c < k)) && c == 13) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && y == 13) && k <= 20)) || (((((cond == 1 && 16 == y) && 16 == c) && (k * y == y * y || c < k)) && y * y * y * 2 + y * y * y * y + y * y == x * 4) && k <= 20) RESULT: Ultimate proved your program to be correct! [2023-02-15 12:31:10,729 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE