./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.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/egcd2-ll_unwindbound10.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 aa34b6970b46b2c3f1bda76d086482188f10831dd44cba913e5171769601c6f3 --- Real Ultimate output --- This is Ultimate 0.2.2-?-a31fd05 [2023-02-15 11:41:16,775 INFO L177 SettingsManager]: Resetting all preferences to default values... [2023-02-15 11:41:16,777 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2023-02-15 11:41:16,822 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2023-02-15 11:41:16,822 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2023-02-15 11:41:16,825 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2023-02-15 11:41:16,826 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2023-02-15 11:41:16,827 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2023-02-15 11:41:16,829 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2023-02-15 11:41:16,832 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2023-02-15 11:41:16,833 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2023-02-15 11:41:16,835 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2023-02-15 11:41:16,835 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2023-02-15 11:41:16,836 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2023-02-15 11:41:16,837 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2023-02-15 11:41:16,838 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2023-02-15 11:41:16,839 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2023-02-15 11:41:16,840 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2023-02-15 11:41:16,841 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2023-02-15 11:41:16,844 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2023-02-15 11:41:16,845 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2023-02-15 11:41:16,846 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2023-02-15 11:41:16,847 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2023-02-15 11:41:16,847 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2023-02-15 11:41:16,853 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2023-02-15 11:41:16,854 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2023-02-15 11:41:16,854 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2023-02-15 11:41:16,855 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2023-02-15 11:41:16,855 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2023-02-15 11:41:16,856 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2023-02-15 11:41:16,856 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2023-02-15 11:41:16,857 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2023-02-15 11:41:16,858 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2023-02-15 11:41:16,858 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2023-02-15 11:41:16,859 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2023-02-15 11:41:16,859 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2023-02-15 11:41:16,859 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2023-02-15 11:41:16,860 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2023-02-15 11:41:16,860 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2023-02-15 11:41:16,860 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2023-02-15 11:41:16,861 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2023-02-15 11:41:16,862 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2023-02-15 11:41:16,884 INFO L113 SettingsManager]: Loading preferences was successful [2023-02-15 11:41:16,884 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2023-02-15 11:41:16,885 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-02-15 11:41:16,885 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-02-15 11:41:16,885 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-02-15 11:41:16,886 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-02-15 11:41:16,886 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-02-15 11:41:16,886 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2023-02-15 11:41:16,886 INFO L138 SettingsManager]: * Use SBE=true [2023-02-15 11:41:16,886 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-02-15 11:41:16,887 INFO L138 SettingsManager]: * sizeof long=4 [2023-02-15 11:41:16,887 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2023-02-15 11:41:16,887 INFO L138 SettingsManager]: * sizeof POINTER=4 [2023-02-15 11:41:16,887 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2023-02-15 11:41:16,887 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-02-15 11:41:16,888 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-02-15 11:41:16,888 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-02-15 11:41:16,888 INFO L138 SettingsManager]: * sizeof long double=12 [2023-02-15 11:41:16,888 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2023-02-15 11:41:16,888 INFO L138 SettingsManager]: * Use constant arrays=true [2023-02-15 11:41:16,888 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-02-15 11:41:16,888 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-02-15 11:41:16,889 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-02-15 11:41:16,889 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2023-02-15 11:41:16,889 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-02-15 11:41:16,889 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-02-15 11:41:16,889 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-02-15 11:41:16,889 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-02-15 11:41:16,889 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2023-02-15 11:41:16,889 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-02-15 11:41:16,890 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-02-15 11:41:16,890 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-02-15 11:41:16,890 INFO L138 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-02-15 11:41:16,890 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-02-15 11:41:16,890 INFO L138 SettingsManager]: * Independence relation used for large block encoding in concurrent analysis=SYNTACTIC [2023-02-15 11:41:16,890 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 -> aa34b6970b46b2c3f1bda76d086482188f10831dd44cba913e5171769601c6f3 [2023-02-15 11:41:17,080 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-02-15 11:41:17,112 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-02-15 11:41:17,113 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-02-15 11:41:17,114 INFO L271 PluginConnector]: Initializing CDTParser... [2023-02-15 11:41:17,114 INFO L275 PluginConnector]: CDTParser initialized [2023-02-15 11:41:17,115 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c [2023-02-15 11:41:18,049 INFO L500 CDTParser]: Created temporary CDT project at NULL [2023-02-15 11:41:18,187 INFO L351 CDTParser]: Found 1 translation units. [2023-02-15 11:41:18,189 INFO L172 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c [2023-02-15 11:41:18,197 INFO L394 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1dd756596/d92131a288064bff89f425c341cb9e92/FLAGd62ebfe40 [2023-02-15 11:41:18,615 INFO L402 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1dd756596/d92131a288064bff89f425c341cb9e92 [2023-02-15 11:41:18,617 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-02-15 11:41:18,618 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2023-02-15 11:41:18,619 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-02-15 11:41:18,619 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-02-15 11:41:18,622 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2023-02-15 11:41:18,622 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.02 11:41:18" (1/1) ... [2023-02-15 11:41:18,623 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1b3f3f34 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18, skipping insertion in model container [2023-02-15 11:41:18,623 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.02 11:41:18" (1/1) ... [2023-02-15 11:41:18,628 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2023-02-15 11:41:18,638 INFO L178 MainTranslator]: Built tables and reachable declarations [2023-02-15 11:41:18,729 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/egcd2-ll_unwindbound10.c[490,503] [2023-02-15 11:41:18,743 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-15 11:41:18,750 INFO L203 MainTranslator]: Completed pre-run [2023-02-15 11:41:18,758 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/egcd2-ll_unwindbound10.c[490,503] [2023-02-15 11:41:18,764 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-15 11:41:18,773 INFO L208 MainTranslator]: Completed translation [2023-02-15 11:41:18,773 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18 WrapperNode [2023-02-15 11:41:18,773 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-02-15 11:41:18,774 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-02-15 11:41:18,774 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-02-15 11:41:18,774 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2023-02-15 11:41:18,779 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18" (1/1) ... [2023-02-15 11:41:18,783 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18" (1/1) ... [2023-02-15 11:41:18,795 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 84 [2023-02-15 11:41:18,796 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-02-15 11:41:18,796 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-02-15 11:41:18,796 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2023-02-15 11:41:18,796 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2023-02-15 11:41:18,802 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18" (1/1) ... [2023-02-15 11:41:18,803 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18" (1/1) ... [2023-02-15 11:41:18,805 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18" (1/1) ... [2023-02-15 11:41:18,806 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18" (1/1) ... [2023-02-15 11:41:18,812 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18" (1/1) ... [2023-02-15 11:41:18,819 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18" (1/1) ... [2023-02-15 11:41:18,820 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18" (1/1) ... [2023-02-15 11:41:18,821 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18" (1/1) ... [2023-02-15 11:41:18,822 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-02-15 11:41:18,822 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-02-15 11:41:18,822 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2023-02-15 11:41:18,823 INFO L275 PluginConnector]: RCFGBuilder initialized [2023-02-15 11:41:18,823 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18" (1/1) ... [2023-02-15 11:41:18,827 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-02-15 11:41:18,834 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:18,847 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 11:41:18,853 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 11:41:18,873 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-02-15 11:41:18,873 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-02-15 11:41:18,873 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-02-15 11:41:18,873 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-02-15 11:41:18,873 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-02-15 11:41:18,873 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-02-15 11:41:18,873 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-02-15 11:41:18,873 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-02-15 11:41:18,916 INFO L235 CfgBuilder]: Building ICFG [2023-02-15 11:41:18,917 INFO L261 CfgBuilder]: Building CFG for each procedure with an implementation [2023-02-15 11:41:19,037 INFO L276 CfgBuilder]: Performing block encoding [2023-02-15 11:41:19,042 INFO L295 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-02-15 11:41:19,042 INFO L300 CfgBuilder]: Removed 2 assume(true) statements. [2023-02-15 11:41:19,043 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.02 11:41:19 BoogieIcfgContainer [2023-02-15 11:41:19,043 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-02-15 11:41:19,045 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-02-15 11:41:19,045 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2023-02-15 11:41:19,047 INFO L275 PluginConnector]: TraceAbstraction initialized [2023-02-15 11:41:19,047 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.02 11:41:18" (1/3) ... [2023-02-15 11:41:19,048 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@785b9684 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.02 11:41:19, skipping insertion in model container [2023-02-15 11:41:19,048 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 11:41:18" (2/3) ... [2023-02-15 11:41:19,048 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@785b9684 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.02 11:41:19, skipping insertion in model container [2023-02-15 11:41:19,048 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.02 11:41:19" (3/3) ... [2023-02-15 11:41:19,049 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound10.c [2023-02-15 11:41:19,096 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-02-15 11:41:19,096 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-02-15 11:41:19,137 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-02-15 11:41:19,143 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;@3d258905, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-02-15 11:41:19,144 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-02-15 11:41:19,151 INFO L276 IsEmpty]: Start isEmpty. Operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-02-15 11:41:19,157 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-02-15 11:41:19,157 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:19,157 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:19,158 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:19,161 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:19,161 INFO L85 PathProgramCache]: Analyzing trace with hash 1022199732, now seen corresponding path program 1 times [2023-02-15 11:41:19,166 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:19,167 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [234426525] [2023-02-15 11:41:19,167 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:19,167 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:19,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:19,264 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:19,266 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [234426525] [2023-02-15 11:41:19,267 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-02-15 11:41:19,267 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [304835816] [2023-02-15 11:41:19,267 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:19,268 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:19,268 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:19,270 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 11:41:19,271 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 11:41:19,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:19,337 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 1 conjunts are in the unsatisfiable core [2023-02-15 11:41:19,341 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:19,361 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-02-15 11:41:19,362 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 11:41:19,363 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [304835816] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 11:41:19,363 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 11:41:19,363 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-02-15 11:41:19,365 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [539227614] [2023-02-15 11:41:19,365 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 11:41:19,369 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-02-15 11:41:19,369 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:19,407 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-02-15 11:41:19,409 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-02-15 11:41:19,411 INFO L87 Difference]: Start difference. First operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-15 11:41:19,427 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:19,427 INFO L93 Difference]: Finished difference Result 65 states and 104 transitions. [2023-02-15 11:41:19,428 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-02-15 11:41:19,429 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2023-02-15 11:41:19,429 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:19,433 INFO L225 Difference]: With dead ends: 65 [2023-02-15 11:41:19,434 INFO L226 Difference]: Without dead ends: 30 [2023-02-15 11:41:19,436 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 27 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 11:41:19,438 INFO L413 NwaCegarLoop]: 45 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, 45 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 11:41:19,439 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 11:41:19,450 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2023-02-15 11:41:19,461 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2023-02-15 11:41:19,461 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 19 states have internal predecessors, (22), 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 11:41:19,464 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 41 transitions. [2023-02-15 11:41:19,465 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 41 transitions. Word has length 28 [2023-02-15 11:41:19,466 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:19,466 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 41 transitions. [2023-02-15 11:41:19,466 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-15 11:41:19,466 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 41 transitions. [2023-02-15 11:41:19,468 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2023-02-15 11:41:19,468 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:19,468 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:19,493 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 11:41:19,673 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 11:41:19,674 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:19,674 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:19,674 INFO L85 PathProgramCache]: Analyzing trace with hash -455220980, now seen corresponding path program 1 times [2023-02-15 11:41:19,674 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:19,675 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1270069480] [2023-02-15 11:41:19,675 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:19,677 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:19,691 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:19,691 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [613730180] [2023-02-15 11:41:19,691 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:19,692 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:19,692 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:19,697 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 11:41:19,699 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 11:41:19,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:19,746 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 3 conjunts are in the unsatisfiable core [2023-02-15 11:41:19,748 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:19,835 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-02-15 11:41:19,835 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 11:41:19,836 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:19,838 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1270069480] [2023-02-15 11:41:19,838 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:19,838 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [613730180] [2023-02-15 11:41:19,839 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [613730180] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 11:41:19,839 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 11:41:19,840 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-02-15 11:41:19,841 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1949433960] [2023-02-15 11:41:19,841 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 11:41:19,842 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-02-15 11:41:19,842 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:19,843 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-02-15 11:41:19,843 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-02-15 11:41:19,844 INFO L87 Difference]: Start difference. First operand 30 states and 41 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-02-15 11:41:19,860 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:19,860 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2023-02-15 11:41:19,860 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-02-15 11:41:19,860 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2023-02-15 11:41:19,861 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:19,861 INFO L225 Difference]: With dead ends: 40 [2023-02-15 11:41:19,861 INFO L226 Difference]: Without dead ends: 32 [2023-02-15 11:41:19,861 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-02-15 11:41:19,862 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 0 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:19,863 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 100 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 11:41:19,863 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2023-02-15 11:41:19,866 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2023-02-15 11:41:19,867 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 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 11:41:19,867 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 43 transitions. [2023-02-15 11:41:19,867 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 43 transitions. Word has length 29 [2023-02-15 11:41:19,868 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:19,868 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 43 transitions. [2023-02-15 11:41:19,868 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-02-15 11:41:19,868 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 43 transitions. [2023-02-15 11:41:19,869 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2023-02-15 11:41:19,869 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:19,869 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:19,876 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 11:41:20,075 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 11:41:20,076 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:20,076 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:20,076 INFO L85 PathProgramCache]: Analyzing trace with hash -1233535180, now seen corresponding path program 1 times [2023-02-15 11:41:20,077 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:20,077 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [848767025] [2023-02-15 11:41:20,077 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:20,077 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:20,086 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:20,086 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2113240602] [2023-02-15 11:41:20,086 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:20,086 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:20,086 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:20,087 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 11:41:20,089 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 11:41:20,142 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:20,143 INFO L263 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-15 11:41:20,145 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:20,212 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-02-15 11:41:20,212 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:41:20,314 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-02-15 11:41:20,314 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:20,314 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [848767025] [2023-02-15 11:41:20,314 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:20,314 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2113240602] [2023-02-15 11:41:20,314 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2113240602] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 11:41:20,314 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 11:41:20,314 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2023-02-15 11:41:20,315 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [39870869] [2023-02-15 11:41:20,315 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 11:41:20,315 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-02-15 11:41:20,315 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:20,316 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-02-15 11:41:20,317 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2023-02-15 11:41:20,317 INFO L87 Difference]: Start difference. First operand 32 states and 43 transitions. Second operand has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-15 11:41:20,380 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:20,380 INFO L93 Difference]: Finished difference Result 49 states and 67 transitions. [2023-02-15 11:41:20,381 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-15 11:41:20,381 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2023-02-15 11:41:20,381 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:20,382 INFO L225 Difference]: With dead ends: 49 [2023-02-15 11:41:20,382 INFO L226 Difference]: Without dead ends: 41 [2023-02-15 11:41:20,382 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 51 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2023-02-15 11:41:20,383 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 29 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:20,383 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 92 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 11:41:20,383 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2023-02-15 11:41:20,387 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 33. [2023-02-15 11:41:20,387 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 20 states have (on average 1.25) internal successors, (25), 21 states have internal predecessors, (25), 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 11:41:20,388 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 44 transitions. [2023-02-15 11:41:20,388 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 44 transitions. Word has length 30 [2023-02-15 11:41:20,388 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:20,388 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 44 transitions. [2023-02-15 11:41:20,388 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-15 11:41:20,388 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2023-02-15 11:41:20,393 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2023-02-15 11:41:20,393 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:20,393 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:20,409 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 11:41:20,602 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 11:41:20,602 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:20,603 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:20,603 INFO L85 PathProgramCache]: Analyzing trace with hash -73118621, now seen corresponding path program 1 times [2023-02-15 11:41:20,603 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:20,603 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [134152921] [2023-02-15 11:41:20,603 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:20,603 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:20,611 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:20,611 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [811539497] [2023-02-15 11:41:20,612 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:20,612 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:20,612 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:20,613 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 11:41:20,615 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 11:41:20,648 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:20,649 INFO L263 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 17 conjunts are in the unsatisfiable core [2023-02-15 11:41:20,658 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:20,719 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-02-15 11:41:20,720 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:41:20,766 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-02-15 11:41:20,766 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:20,767 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [134152921] [2023-02-15 11:41:20,767 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:20,767 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [811539497] [2023-02-15 11:41:20,767 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [811539497] provided 1 perfect and 1 imperfect interpolant sequences [2023-02-15 11:41:20,767 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-02-15 11:41:20,767 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 12 [2023-02-15 11:41:20,767 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1309686674] [2023-02-15 11:41:20,768 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 11:41:20,768 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-15 11:41:20,768 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:20,768 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-15 11:41:20,768 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=107, Unknown=0, NotChecked=0, Total=132 [2023-02-15 11:41:20,769 INFO L87 Difference]: Start difference. First operand 33 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-02-15 11:41:20,805 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:20,806 INFO L93 Difference]: Finished difference Result 39 states and 49 transitions. [2023-02-15 11:41:20,806 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-15 11:41:20,806 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2023-02-15 11:41:20,806 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:20,807 INFO L225 Difference]: With dead ends: 39 [2023-02-15 11:41:20,807 INFO L226 Difference]: Without dead ends: 37 [2023-02-15 11:41:20,807 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 52 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2023-02-15 11:41:20,808 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 8 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:20,808 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 114 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 11:41:20,808 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2023-02-15 11:41:20,812 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2023-02-15 11:41:20,812 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 24 states have internal predecessors, (28), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-02-15 11:41:20,813 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 47 transitions. [2023-02-15 11:41:20,813 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 47 transitions. Word has length 32 [2023-02-15 11:41:20,813 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:20,813 INFO L495 AbstractCegarLoop]: Abstraction has 37 states and 47 transitions. [2023-02-15 11:41:20,813 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-02-15 11:41:20,813 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 47 transitions. [2023-02-15 11:41:20,814 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2023-02-15 11:41:20,814 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:20,814 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:20,828 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 11:41:21,020 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 11:41:21,021 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:21,021 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:21,021 INFO L85 PathProgramCache]: Analyzing trace with hash 96561445, now seen corresponding path program 1 times [2023-02-15 11:41:21,021 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:21,021 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [309433907] [2023-02-15 11:41:21,021 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:21,021 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:21,035 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:21,035 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [275924849] [2023-02-15 11:41:21,035 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:21,035 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:21,035 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:21,036 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 11:41:21,038 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 11:41:21,076 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:21,077 INFO L263 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 5 conjunts are in the unsatisfiable core [2023-02-15 11:41:21,078 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:21,110 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-02-15 11:41:21,110 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 11:41:21,110 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:21,111 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [309433907] [2023-02-15 11:41:21,111 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:21,111 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [275924849] [2023-02-15 11:41:21,111 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [275924849] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 11:41:21,111 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 11:41:21,111 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-02-15 11:41:21,111 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1255729501] [2023-02-15 11:41:21,111 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 11:41:21,112 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-15 11:41:21,112 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:21,112 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-15 11:41:21,116 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-02-15 11:41:21,117 INFO L87 Difference]: Start difference. First operand 37 states and 47 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-02-15 11:41:21,128 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:21,129 INFO L93 Difference]: Finished difference Result 62 states and 80 transitions. [2023-02-15 11:41:21,129 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-02-15 11:41:21,129 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 35 [2023-02-15 11:41:21,129 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:21,130 INFO L225 Difference]: With dead ends: 62 [2023-02-15 11:41:21,130 INFO L226 Difference]: Without dead ends: 39 [2023-02-15 11:41:21,130 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-02-15 11:41:21,133 INFO L413 NwaCegarLoop]: 38 mSDtfsCounter, 0 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:21,136 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 100 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 11:41:21,138 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2023-02-15 11:41:21,143 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2023-02-15 11:41:21,143 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 25 states have (on average 1.2) internal successors, (30), 26 states have internal predecessors, (30), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-02-15 11:41:21,144 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 49 transitions. [2023-02-15 11:41:21,144 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 49 transitions. Word has length 35 [2023-02-15 11:41:21,144 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:21,144 INFO L495 AbstractCegarLoop]: Abstraction has 39 states and 49 transitions. [2023-02-15 11:41:21,144 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-02-15 11:41:21,144 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 49 transitions. [2023-02-15 11:41:21,146 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2023-02-15 11:41:21,147 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:21,147 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:21,165 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 11:41:21,353 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 11:41:21,353 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:21,353 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:21,353 INFO L85 PathProgramCache]: Analyzing trace with hash 433790877, now seen corresponding path program 1 times [2023-02-15 11:41:21,353 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:21,353 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1930262225] [2023-02-15 11:41:21,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:21,354 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:21,361 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:21,361 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [376910578] [2023-02-15 11:41:21,361 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:21,361 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:21,361 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:21,362 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 11:41:21,364 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 11:41:21,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:21,414 INFO L263 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 28 conjunts are in the unsatisfiable core [2023-02-15 11:41:21,416 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:21,610 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 1 proven. 13 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-02-15 11:41:21,611 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:41:21,702 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-02-15 11:41:21,702 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:21,702 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1930262225] [2023-02-15 11:41:21,702 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:21,702 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [376910578] [2023-02-15 11:41:21,702 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [376910578] provided 1 perfect and 1 imperfect interpolant sequences [2023-02-15 11:41:21,702 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-02-15 11:41:21,703 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [12] total 14 [2023-02-15 11:41:21,703 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [161844778] [2023-02-15 11:41:21,703 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 11:41:21,703 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-15 11:41:21,703 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:21,703 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-15 11:41:21,704 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=148, Unknown=0, NotChecked=0, Total=182 [2023-02-15 11:41:21,704 INFO L87 Difference]: Start difference. First operand 39 states and 49 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-02-15 11:41:21,744 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:21,744 INFO L93 Difference]: Finished difference Result 53 states and 68 transitions. [2023-02-15 11:41:21,744 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-15 11:41:21,744 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 37 [2023-02-15 11:41:21,745 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:21,746 INFO L225 Difference]: With dead ends: 53 [2023-02-15 11:41:21,746 INFO L226 Difference]: Without dead ends: 51 [2023-02-15 11:41:21,747 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 60 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=172, Unknown=0, NotChecked=0, Total=210 [2023-02-15 11:41:21,749 INFO L413 NwaCegarLoop]: 43 mSDtfsCounter, 7 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:21,749 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 140 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 11:41:21,750 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2023-02-15 11:41:21,765 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 50. [2023-02-15 11:41:21,765 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 31 states have (on average 1.2258064516129032) internal successors, (38), 32 states have internal predecessors, (38), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-02-15 11:41:21,767 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 65 transitions. [2023-02-15 11:41:21,767 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 65 transitions. Word has length 37 [2023-02-15 11:41:21,767 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:21,767 INFO L495 AbstractCegarLoop]: Abstraction has 50 states and 65 transitions. [2023-02-15 11:41:21,769 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-02-15 11:41:21,769 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 65 transitions. [2023-02-15 11:41:21,774 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2023-02-15 11:41:21,774 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:21,774 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:21,797 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 11:41:21,979 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 11:41:21,979 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:21,979 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:21,979 INFO L85 PathProgramCache]: Analyzing trace with hash -553232285, now seen corresponding path program 1 times [2023-02-15 11:41:21,979 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:21,980 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [723626360] [2023-02-15 11:41:21,980 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:21,980 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:21,988 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:21,991 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [956446749] [2023-02-15 11:41:21,991 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:21,991 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:21,991 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:21,992 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 11:41:21,994 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 11:41:22,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:22,032 INFO L263 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 23 conjunts are in the unsatisfiable core [2023-02-15 11:41:22,038 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:22,182 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 3 proven. 13 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-02-15 11:41:22,182 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:41:22,254 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-02-15 11:41:22,254 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:22,254 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [723626360] [2023-02-15 11:41:22,254 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:22,255 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [956446749] [2023-02-15 11:41:22,255 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [956446749] provided 1 perfect and 1 imperfect interpolant sequences [2023-02-15 11:41:22,255 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-02-15 11:41:22,255 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [11] total 13 [2023-02-15 11:41:22,255 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [730693402] [2023-02-15 11:41:22,255 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 11:41:22,256 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-15 11:41:22,256 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:22,257 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-15 11:41:22,257 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2023-02-15 11:41:22,257 INFO L87 Difference]: Start difference. First operand 50 states and 65 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-02-15 11:41:22,300 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:22,301 INFO L93 Difference]: Finished difference Result 57 states and 71 transitions. [2023-02-15 11:41:22,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-15 11:41:22,301 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 42 [2023-02-15 11:41:22,301 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:22,303 INFO L225 Difference]: With dead ends: 57 [2023-02-15 11:41:22,303 INFO L226 Difference]: Without dead ends: 55 [2023-02-15 11:41:22,303 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 71 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=33, Invalid=149, Unknown=0, NotChecked=0, Total=182 [2023-02-15 11:41:22,304 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 7 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:22,304 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 131 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 11:41:22,305 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2023-02-15 11:41:22,318 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 54. [2023-02-15 11:41:22,318 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 34 states have (on average 1.2058823529411764) internal successors, (41), 35 states have internal predecessors, (41), 14 states have call successors, (14), 5 states have call predecessors, (14), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-02-15 11:41:22,320 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 68 transitions. [2023-02-15 11:41:22,321 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 68 transitions. Word has length 42 [2023-02-15 11:41:22,322 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:22,322 INFO L495 AbstractCegarLoop]: Abstraction has 54 states and 68 transitions. [2023-02-15 11:41:22,322 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-02-15 11:41:22,322 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 68 transitions. [2023-02-15 11:41:22,322 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2023-02-15 11:41:22,322 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:22,323 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:22,343 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-02-15 11:41:22,529 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 11:41:22,529 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:22,529 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:22,529 INFO L85 PathProgramCache]: Analyzing trace with hash 2115683101, now seen corresponding path program 1 times [2023-02-15 11:41:22,530 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:22,530 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [88741752] [2023-02-15 11:41:22,530 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:22,530 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:22,536 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:22,537 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [985791758] [2023-02-15 11:41:22,537 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:22,537 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:22,537 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:22,538 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 11:41:22,540 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 11:41:22,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:22,575 INFO L263 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 19 conjunts are in the unsatisfiable core [2023-02-15 11:41:22,576 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:22,652 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-02-15 11:41:22,652 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:41:22,759 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:22,759 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [88741752] [2023-02-15 11:41:22,759 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:22,760 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [985791758] [2023-02-15 11:41:22,760 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [985791758] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-15 11:41:22,760 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-15 11:41:22,760 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2023-02-15 11:41:22,760 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1921320642] [2023-02-15 11:41:22,760 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-15 11:41:22,761 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-02-15 11:41:22,761 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:22,761 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-02-15 11:41:22,761 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2023-02-15 11:41:22,761 INFO L87 Difference]: Start difference. First operand 54 states and 68 transitions. Second operand has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-02-15 11:41:22,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:22,857 INFO L93 Difference]: Finished difference Result 61 states and 74 transitions. [2023-02-15 11:41:22,857 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-02-15 11:41:22,858 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 47 [2023-02-15 11:41:22,858 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:22,859 INFO L225 Difference]: With dead ends: 61 [2023-02-15 11:41:22,859 INFO L226 Difference]: Without dead ends: 59 [2023-02-15 11:41:22,859 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2023-02-15 11:41:22,860 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 13 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 104 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 104 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:22,860 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 115 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 104 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 11:41:22,861 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2023-02-15 11:41:22,872 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2023-02-15 11:41:22,873 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 37 states have (on average 1.1891891891891893) internal successors, (44), 38 states have internal predecessors, (44), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-02-15 11:41:22,873 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 71 transitions. [2023-02-15 11:41:22,873 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 71 transitions. Word has length 47 [2023-02-15 11:41:22,874 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:22,874 INFO L495 AbstractCegarLoop]: Abstraction has 58 states and 71 transitions. [2023-02-15 11:41:22,874 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-02-15 11:41:22,874 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 71 transitions. [2023-02-15 11:41:22,875 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2023-02-15 11:41:22,875 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:22,875 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:22,883 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 11:41:23,083 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 11:41:23,084 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:23,085 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:23,085 INFO L85 PathProgramCache]: Analyzing trace with hash -879665460, now seen corresponding path program 1 times [2023-02-15 11:41:23,085 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:23,085 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1214937718] [2023-02-15 11:41:23,085 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:23,085 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:23,101 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:23,103 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1191311751] [2023-02-15 11:41:23,103 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:23,103 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:23,103 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:23,107 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 11:41:23,109 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 11:41:23,146 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:23,148 INFO L263 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-15 11:41:23,149 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:23,198 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-02-15 11:41:23,199 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:41:23,242 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-02-15 11:41:23,242 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:23,243 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1214937718] [2023-02-15 11:41:23,243 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:23,243 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1191311751] [2023-02-15 11:41:23,243 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1191311751] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 11:41:23,243 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 11:41:23,243 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 10 [2023-02-15 11:41:23,243 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [463499133] [2023-02-15 11:41:23,243 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 11:41:23,244 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-02-15 11:41:23,244 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:23,244 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-02-15 11:41:23,244 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2023-02-15 11:41:23,245 INFO L87 Difference]: Start difference. First operand 58 states and 71 transitions. Second operand has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2023-02-15 11:41:23,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:23,345 INFO L93 Difference]: Finished difference Result 211 states and 250 transitions. [2023-02-15 11:41:23,345 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-02-15 11:41:23,346 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 56 [2023-02-15 11:41:23,346 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:23,347 INFO L225 Difference]: With dead ends: 211 [2023-02-15 11:41:23,347 INFO L226 Difference]: Without dead ends: 203 [2023-02-15 11:41:23,348 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 102 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2023-02-15 11:41:23,348 INFO L413 NwaCegarLoop]: 57 mSDtfsCounter, 81 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 80 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 98 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 80 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:23,348 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [81 Valid, 180 Invalid, 98 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 80 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 11:41:23,349 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2023-02-15 11:41:23,365 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 195. [2023-02-15 11:41:23,366 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 195 states, 125 states have (on average 1.192) internal successors, (149), 129 states have internal predecessors, (149), 44 states have call successors, (44), 25 states have call predecessors, (44), 25 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2023-02-15 11:41:23,367 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 195 states to 195 states and 233 transitions. [2023-02-15 11:41:23,367 INFO L78 Accepts]: Start accepts. Automaton has 195 states and 233 transitions. Word has length 56 [2023-02-15 11:41:23,367 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:23,367 INFO L495 AbstractCegarLoop]: Abstraction has 195 states and 233 transitions. [2023-02-15 11:41:23,368 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2023-02-15 11:41:23,368 INFO L276 IsEmpty]: Start isEmpty. Operand 195 states and 233 transitions. [2023-02-15 11:41:23,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2023-02-15 11:41:23,368 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:23,368 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:23,387 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2023-02-15 11:41:23,572 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 11:41:23,573 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:23,573 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:23,573 INFO L85 PathProgramCache]: Analyzing trace with hash -1506412172, now seen corresponding path program 1 times [2023-02-15 11:41:23,573 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:23,573 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2035446321] [2023-02-15 11:41:23,573 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:23,573 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:23,579 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:23,580 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1452552126] [2023-02-15 11:41:23,580 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:23,580 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:23,580 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:23,581 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 11:41:23,583 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 11:41:23,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:23,628 INFO L263 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 9 conjunts are in the unsatisfiable core [2023-02-15 11:41:23,629 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:23,675 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2023-02-15 11:41:23,675 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:41:23,743 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2023-02-15 11:41:23,743 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:23,743 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2035446321] [2023-02-15 11:41:23,743 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:23,743 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1452552126] [2023-02-15 11:41:23,744 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1452552126] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 11:41:23,744 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 11:41:23,744 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2023-02-15 11:41:23,744 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [368998349] [2023-02-15 11:41:23,744 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 11:41:23,744 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-02-15 11:41:23,748 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:23,749 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-02-15 11:41:23,749 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2023-02-15 11:41:23,749 INFO L87 Difference]: Start difference. First operand 195 states and 233 transitions. Second operand has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2023-02-15 11:41:23,964 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:23,964 INFO L93 Difference]: Finished difference Result 279 states and 364 transitions. [2023-02-15 11:41:23,964 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-02-15 11:41:23,964 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 57 [2023-02-15 11:41:23,964 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:23,967 INFO L225 Difference]: With dead ends: 279 [2023-02-15 11:41:23,967 INFO L226 Difference]: Without dead ends: 259 [2023-02-15 11:41:23,969 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 101 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2023-02-15 11:41:23,970 INFO L413 NwaCegarLoop]: 66 mSDtfsCounter, 70 mSDsluCounter, 220 mSDsCounter, 0 mSdLazyCounter, 160 mSolverCounterSat, 63 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 75 SdHoareTripleChecker+Valid, 286 SdHoareTripleChecker+Invalid, 223 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 63 IncrementalHoareTripleChecker+Valid, 160 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:23,970 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [75 Valid, 286 Invalid, 223 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [63 Valid, 160 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 11:41:23,971 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states. [2023-02-15 11:41:23,994 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 235. [2023-02-15 11:41:23,995 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 235 states, 152 states have (on average 1.2236842105263157) internal successors, (186), 155 states have internal predecessors, (186), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2023-02-15 11:41:23,996 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 299 transitions. [2023-02-15 11:41:23,996 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 299 transitions. Word has length 57 [2023-02-15 11:41:23,996 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:23,996 INFO L495 AbstractCegarLoop]: Abstraction has 235 states and 299 transitions. [2023-02-15 11:41:23,996 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2023-02-15 11:41:23,996 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 299 transitions. [2023-02-15 11:41:23,997 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2023-02-15 11:41:23,997 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:23,997 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:24,004 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 11:41:24,201 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 11:41:24,201 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:24,201 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:24,201 INFO L85 PathProgramCache]: Analyzing trace with hash -1869160295, now seen corresponding path program 1 times [2023-02-15 11:41:24,202 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:24,202 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [255977738] [2023-02-15 11:41:24,202 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:24,202 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:24,208 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:24,208 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2092399129] [2023-02-15 11:41:24,208 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:24,208 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:24,208 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:24,213 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 11:41:24,221 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 11:41:24,250 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:24,253 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-15 11:41:24,254 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:24,304 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-02-15 11:41:24,304 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:41:24,350 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-02-15 11:41:24,350 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:24,350 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [255977738] [2023-02-15 11:41:24,350 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:24,350 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2092399129] [2023-02-15 11:41:24,350 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2092399129] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 11:41:24,350 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 11:41:24,350 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 10 [2023-02-15 11:41:24,350 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [286075444] [2023-02-15 11:41:24,351 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 11:41:24,351 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-02-15 11:41:24,351 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:24,351 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-02-15 11:41:24,351 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2023-02-15 11:41:24,351 INFO L87 Difference]: Start difference. First operand 235 states and 299 transitions. Second operand has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2023-02-15 11:41:24,453 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:24,453 INFO L93 Difference]: Finished difference Result 344 states and 448 transitions. [2023-02-15 11:41:24,453 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-02-15 11:41:24,453 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 59 [2023-02-15 11:41:24,453 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:24,454 INFO L225 Difference]: With dead ends: 344 [2023-02-15 11:41:24,454 INFO L226 Difference]: Without dead ends: 248 [2023-02-15 11:41:24,455 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 108 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2023-02-15 11:41:24,455 INFO L413 NwaCegarLoop]: 56 mSDtfsCounter, 59 mSDsluCounter, 196 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 252 SdHoareTripleChecker+Invalid, 92 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:24,455 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 252 Invalid, 92 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 11:41:24,456 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 248 states. [2023-02-15 11:41:24,471 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 248 to 244. [2023-02-15 11:41:24,472 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 244 states, 161 states have (on average 1.173913043478261) internal successors, (189), 164 states have internal predecessors, (189), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2023-02-15 11:41:24,473 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 244 states to 244 states and 302 transitions. [2023-02-15 11:41:24,473 INFO L78 Accepts]: Start accepts. Automaton has 244 states and 302 transitions. Word has length 59 [2023-02-15 11:41:24,473 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:24,473 INFO L495 AbstractCegarLoop]: Abstraction has 244 states and 302 transitions. [2023-02-15 11:41:24,473 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2023-02-15 11:41:24,473 INFO L276 IsEmpty]: Start isEmpty. Operand 244 states and 302 transitions. [2023-02-15 11:41:24,474 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2023-02-15 11:41:24,474 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:24,474 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:24,480 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 11:41:24,680 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 11:41:24,680 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:24,681 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:24,681 INFO L85 PathProgramCache]: Analyzing trace with hash 991223133, now seen corresponding path program 1 times [2023-02-15 11:41:24,681 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:24,681 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [399901631] [2023-02-15 11:41:24,681 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:24,681 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:24,687 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:24,687 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [163234829] [2023-02-15 11:41:24,687 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:24,687 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:24,687 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:24,688 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 11:41:24,690 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-02-15 11:41:24,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:24,740 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 27 conjunts are in the unsatisfiable core [2023-02-15 11:41:24,743 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:24,854 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 21 proven. 8 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2023-02-15 11:41:24,854 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:41:24,947 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2023-02-15 11:41:24,948 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:24,948 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [399901631] [2023-02-15 11:41:24,948 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:24,948 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [163234829] [2023-02-15 11:41:24,948 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [163234829] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 11:41:24,948 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 11:41:24,948 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 6] total 12 [2023-02-15 11:41:24,948 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1343407128] [2023-02-15 11:41:24,948 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 11:41:24,949 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-02-15 11:41:24,949 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:24,950 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-02-15 11:41:24,950 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2023-02-15 11:41:24,950 INFO L87 Difference]: Start difference. First operand 244 states and 302 transitions. Second operand has 12 states, 12 states have (on average 3.5) internal successors, (42), 11 states have internal predecessors, (42), 6 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2023-02-15 11:41:25,305 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:25,305 INFO L93 Difference]: Finished difference Result 330 states and 429 transitions. [2023-02-15 11:41:25,305 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-02-15 11:41:25,305 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.5) internal successors, (42), 11 states have internal predecessors, (42), 6 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 64 [2023-02-15 11:41:25,305 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:25,307 INFO L225 Difference]: With dead ends: 330 [2023-02-15 11:41:25,307 INFO L226 Difference]: Without dead ends: 324 [2023-02-15 11:41:25,308 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 116 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=57, Invalid=215, Unknown=0, NotChecked=0, Total=272 [2023-02-15 11:41:25,308 INFO L413 NwaCegarLoop]: 50 mSDtfsCounter, 31 mSDsluCounter, 229 mSDsCounter, 0 mSdLazyCounter, 367 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 279 SdHoareTripleChecker+Invalid, 396 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 367 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:25,308 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 279 Invalid, 396 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 367 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-02-15 11:41:25,309 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 324 states. [2023-02-15 11:41:25,336 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 324 to 291. [2023-02-15 11:41:25,337 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 291 states, 194 states have (on average 1.1958762886597938) internal successors, (232), 203 states have internal predecessors, (232), 69 states have call successors, (69), 27 states have call predecessors, (69), 27 states have return successors, (65), 60 states have call predecessors, (65), 65 states have call successors, (65) [2023-02-15 11:41:25,339 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 291 states to 291 states and 366 transitions. [2023-02-15 11:41:25,339 INFO L78 Accepts]: Start accepts. Automaton has 291 states and 366 transitions. Word has length 64 [2023-02-15 11:41:25,339 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:25,339 INFO L495 AbstractCegarLoop]: Abstraction has 291 states and 366 transitions. [2023-02-15 11:41:25,339 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.5) internal successors, (42), 11 states have internal predecessors, (42), 6 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2023-02-15 11:41:25,339 INFO L276 IsEmpty]: Start isEmpty. Operand 291 states and 366 transitions. [2023-02-15 11:41:25,340 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2023-02-15 11:41:25,340 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:25,340 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:25,344 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-02-15 11:41:25,544 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-02-15 11:41:25,545 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:25,545 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:25,545 INFO L85 PathProgramCache]: Analyzing trace with hash 1694315171, now seen corresponding path program 2 times [2023-02-15 11:41:25,545 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:25,545 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [635449861] [2023-02-15 11:41:25,545 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:25,545 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:25,559 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:25,559 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1905731105] [2023-02-15 11:41:25,559 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-15 11:41:25,559 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:25,560 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:25,560 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 11:41:25,570 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-02-15 11:41:25,610 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-15 11:41:25,610 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 11:41:25,612 INFO L263 TraceCheckSpWp]: Trace formula consists of 195 conjuncts, 41 conjunts are in the unsatisfiable core [2023-02-15 11:41:25,613 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:25,935 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 20 proven. 24 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-02-15 11:41:25,935 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:41:30,012 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:30,012 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [635449861] [2023-02-15 11:41:30,012 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:30,012 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1905731105] [2023-02-15 11:41:30,012 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1905731105] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-15 11:41:30,012 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-15 11:41:30,012 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2023-02-15 11:41:30,012 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1060010639] [2023-02-15 11:41:30,012 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-15 11:41:30,012 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-02-15 11:41:30,013 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:30,013 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-02-15 11:41:30,013 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=286, Unknown=0, NotChecked=0, Total=342 [2023-02-15 11:41:30,013 INFO L87 Difference]: Start difference. First operand 291 states and 366 transitions. Second operand has 14 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 12 states have internal predecessors, (30), 5 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) [2023-02-15 11:41:30,417 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:30,417 INFO L93 Difference]: Finished difference Result 315 states and 393 transitions. [2023-02-15 11:41:30,417 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-02-15 11:41:30,417 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 12 states have internal predecessors, (30), 5 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) Word has length 69 [2023-02-15 11:41:30,417 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:30,418 INFO L225 Difference]: With dead ends: 315 [2023-02-15 11:41:30,418 INFO L226 Difference]: Without dead ends: 313 [2023-02-15 11:41:30,419 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 72 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 81 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=93, Invalid=459, Unknown=0, NotChecked=0, Total=552 [2023-02-15 11:41:30,419 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 67 mSDsluCounter, 166 mSDsCounter, 0 mSdLazyCounter, 416 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 78 SdHoareTripleChecker+Valid, 199 SdHoareTripleChecker+Invalid, 448 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 416 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:30,419 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [78 Valid, 199 Invalid, 448 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 416 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-02-15 11:41:30,420 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 313 states. [2023-02-15 11:41:30,442 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 313 to 310. [2023-02-15 11:41:30,443 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 310 states, 206 states have (on average 1.1941747572815533) internal successors, (246), 215 states have internal predecessors, (246), 73 states have call successors, (73), 30 states have call predecessors, (73), 30 states have return successors, (69), 64 states have call predecessors, (69), 69 states have call successors, (69) [2023-02-15 11:41:30,444 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 310 states to 310 states and 388 transitions. [2023-02-15 11:41:30,444 INFO L78 Accepts]: Start accepts. Automaton has 310 states and 388 transitions. Word has length 69 [2023-02-15 11:41:30,444 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:30,444 INFO L495 AbstractCegarLoop]: Abstraction has 310 states and 388 transitions. [2023-02-15 11:41:30,444 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 12 states have internal predecessors, (30), 5 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) [2023-02-15 11:41:30,444 INFO L276 IsEmpty]: Start isEmpty. Operand 310 states and 388 transitions. [2023-02-15 11:41:30,448 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2023-02-15 11:41:30,448 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:30,448 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:30,457 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-02-15 11:41:30,657 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-02-15 11:41:30,657 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:30,657 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:30,657 INFO L85 PathProgramCache]: Analyzing trace with hash -1349365539, now seen corresponding path program 3 times [2023-02-15 11:41:30,657 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:30,657 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [326544856] [2023-02-15 11:41:30,658 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:30,658 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:30,670 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:30,670 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1176153119] [2023-02-15 11:41:30,670 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-15 11:41:30,670 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:30,670 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:30,675 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 11:41:30,678 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-02-15 11:41:30,716 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-02-15 11:41:30,716 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 11:41:30,718 INFO L263 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 42 conjunts are in the unsatisfiable core [2023-02-15 11:41:30,719 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:31,010 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 40 proven. 10 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2023-02-15 11:41:31,010 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:41:33,398 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:33,398 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [326544856] [2023-02-15 11:41:33,398 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:33,398 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1176153119] [2023-02-15 11:41:33,398 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1176153119] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-15 11:41:33,398 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-15 11:41:33,398 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2023-02-15 11:41:33,398 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1587425966] [2023-02-15 11:41:33,398 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-15 11:41:33,399 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-02-15 11:41:33,399 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:33,400 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-02-15 11:41:33,400 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=259, Unknown=1, NotChecked=0, Total=306 [2023-02-15 11:41:33,400 INFO L87 Difference]: Start difference. First operand 310 states and 388 transitions. Second operand has 13 states, 12 states have (on average 2.5) internal successors, (30), 12 states have internal predecessors, (30), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2023-02-15 11:41:34,007 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:34,007 INFO L93 Difference]: Finished difference Result 327 states and 404 transitions. [2023-02-15 11:41:34,007 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-02-15 11:41:34,008 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.5) internal successors, (30), 12 states have internal predecessors, (30), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 74 [2023-02-15 11:41:34,008 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:34,010 INFO L225 Difference]: With dead ends: 327 [2023-02-15 11:41:34,010 INFO L226 Difference]: Without dead ends: 323 [2023-02-15 11:41:34,010 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=71, Invalid=390, Unknown=1, NotChecked=0, Total=462 [2023-02-15 11:41:34,011 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 32 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 447 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 219 SdHoareTripleChecker+Invalid, 456 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 447 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:34,011 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 219 Invalid, 456 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 447 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-02-15 11:41:34,011 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 323 states. [2023-02-15 11:41:34,049 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 323 to 320. [2023-02-15 11:41:34,050 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 320 states, 214 states have (on average 1.1822429906542056) internal successors, (253), 222 states have internal predecessors, (253), 73 states have call successors, (73), 33 states have call predecessors, (73), 32 states have return successors, (69), 64 states have call predecessors, (69), 69 states have call successors, (69) [2023-02-15 11:41:34,051 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 320 states to 320 states and 395 transitions. [2023-02-15 11:41:34,051 INFO L78 Accepts]: Start accepts. Automaton has 320 states and 395 transitions. Word has length 74 [2023-02-15 11:41:34,051 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:34,052 INFO L495 AbstractCegarLoop]: Abstraction has 320 states and 395 transitions. [2023-02-15 11:41:34,052 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.5) internal successors, (30), 12 states have internal predecessors, (30), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2023-02-15 11:41:34,052 INFO L276 IsEmpty]: Start isEmpty. Operand 320 states and 395 transitions. [2023-02-15 11:41:34,052 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2023-02-15 11:41:34,052 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:34,053 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:34,067 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2023-02-15 11:41:34,257 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:34,257 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:34,258 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:34,258 INFO L85 PathProgramCache]: Analyzing trace with hash -484140586, now seen corresponding path program 1 times [2023-02-15 11:41:34,258 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:34,258 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [754773769] [2023-02-15 11:41:34,258 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:34,258 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:34,272 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:34,273 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [858624739] [2023-02-15 11:41:34,273 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:34,273 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:34,273 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:34,274 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 11:41:34,274 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2023-02-15 11:41:34,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:34,321 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 43 conjunts are in the unsatisfiable core [2023-02-15 11:41:34,323 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:34,688 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 19 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2023-02-15 11:41:34,688 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:41:35,435 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2023-02-15 11:41:35,435 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:35,435 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [754773769] [2023-02-15 11:41:35,435 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:35,435 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [858624739] [2023-02-15 11:41:35,436 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [858624739] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 11:41:35,436 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 11:41:35,436 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2023-02-15 11:41:35,436 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [193155064] [2023-02-15 11:41:35,436 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 11:41:35,436 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-02-15 11:41:35,436 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:35,437 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-02-15 11:41:35,437 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2023-02-15 11:41:35,437 INFO L87 Difference]: Start difference. First operand 320 states and 395 transitions. Second operand has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2023-02-15 11:41:46,530 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:46,531 INFO L93 Difference]: Finished difference Result 454 states and 601 transitions. [2023-02-15 11:41:46,531 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2023-02-15 11:41:46,531 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 80 [2023-02-15 11:41:46,532 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:46,533 INFO L225 Difference]: With dead ends: 454 [2023-02-15 11:41:46,533 INFO L226 Difference]: Without dead ends: 443 [2023-02-15 11:41:46,534 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 182 GetRequests, 139 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 399 ImplicationChecksByTransitivity, 7.6s TimeCoverageRelationStatistics Valid=375, Invalid=1605, Unknown=0, NotChecked=0, Total=1980 [2023-02-15 11:41:46,534 INFO L413 NwaCegarLoop]: 85 mSDtfsCounter, 154 mSDsluCounter, 506 mSDsCounter, 0 mSdLazyCounter, 909 mSolverCounterSat, 189 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 158 SdHoareTripleChecker+Valid, 591 SdHoareTripleChecker+Invalid, 1098 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 189 IncrementalHoareTripleChecker+Valid, 909 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.9s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:46,535 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [158 Valid, 591 Invalid, 1098 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [189 Valid, 909 Invalid, 0 Unknown, 0 Unchecked, 3.9s Time] [2023-02-15 11:41:46,535 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 443 states. [2023-02-15 11:41:46,592 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 443 to 410. [2023-02-15 11:41:46,593 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 410 states, 272 states have (on average 1.2316176470588236) internal successors, (335), 281 states have internal predecessors, (335), 103 states have call successors, (103), 34 states have call predecessors, (103), 34 states have return successors, (101), 94 states have call predecessors, (101), 101 states have call successors, (101) [2023-02-15 11:41:46,595 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 410 states to 410 states and 539 transitions. [2023-02-15 11:41:46,595 INFO L78 Accepts]: Start accepts. Automaton has 410 states and 539 transitions. Word has length 80 [2023-02-15 11:41:46,595 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:46,595 INFO L495 AbstractCegarLoop]: Abstraction has 410 states and 539 transitions. [2023-02-15 11:41:46,595 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2023-02-15 11:41:46,595 INFO L276 IsEmpty]: Start isEmpty. Operand 410 states and 539 transitions. [2023-02-15 11:41:46,596 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2023-02-15 11:41:46,596 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:46,596 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:46,601 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2023-02-15 11:41:46,801 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-02-15 11:41:46,802 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:46,802 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:46,802 INFO L85 PathProgramCache]: Analyzing trace with hash 164622435, now seen corresponding path program 4 times [2023-02-15 11:41:46,802 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:46,802 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1664403250] [2023-02-15 11:41:46,802 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:46,802 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:46,809 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:46,809 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [273081984] [2023-02-15 11:41:46,809 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-02-15 11:41:46,809 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:46,809 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:46,810 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 11:41:46,811 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2023-02-15 11:41:46,858 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-02-15 11:41:46,858 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 11:41:46,859 INFO L263 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 5 conjunts are in the unsatisfiable core [2023-02-15 11:41:46,861 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:46,881 INFO L134 CoverageAnalysis]: Checked inductivity of 251 backedges. 107 proven. 0 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2023-02-15 11:41:46,881 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 11:41:46,881 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:46,881 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1664403250] [2023-02-15 11:41:46,881 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:46,882 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [273081984] [2023-02-15 11:41:46,882 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [273081984] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 11:41:46,882 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 11:41:46,882 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-02-15 11:41:46,882 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1265613105] [2023-02-15 11:41:46,882 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 11:41:46,882 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-15 11:41:46,882 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:46,883 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-15 11:41:46,883 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-02-15 11:41:46,883 INFO L87 Difference]: Start difference. First operand 410 states and 539 transitions. Second operand has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) [2023-02-15 11:41:46,991 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:41:46,992 INFO L93 Difference]: Finished difference Result 623 states and 882 transitions. [2023-02-15 11:41:46,992 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-15 11:41:46,992 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) Word has length 96 [2023-02-15 11:41:46,992 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:41:46,994 INFO L225 Difference]: With dead ends: 623 [2023-02-15 11:41:46,994 INFO L226 Difference]: Without dead ends: 448 [2023-02-15 11:41:46,995 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2023-02-15 11:41:46,995 INFO L413 NwaCegarLoop]: 58 mSDtfsCounter, 13 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 76 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 11:41:46,995 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 163 Invalid, 76 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 11:41:46,996 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 448 states. [2023-02-15 11:41:47,038 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 448 to 405. [2023-02-15 11:41:47,038 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 405 states, 265 states have (on average 1.230188679245283) internal successors, (326), 271 states have internal predecessors, (326), 105 states have call successors, (105), 34 states have call predecessors, (105), 34 states have return successors, (103), 99 states have call predecessors, (103), 103 states have call successors, (103) [2023-02-15 11:41:47,039 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 405 states to 405 states and 534 transitions. [2023-02-15 11:41:47,040 INFO L78 Accepts]: Start accepts. Automaton has 405 states and 534 transitions. Word has length 96 [2023-02-15 11:41:47,040 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:41:47,040 INFO L495 AbstractCegarLoop]: Abstraction has 405 states and 534 transitions. [2023-02-15 11:41:47,040 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) [2023-02-15 11:41:47,040 INFO L276 IsEmpty]: Start isEmpty. Operand 405 states and 534 transitions. [2023-02-15 11:41:47,041 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2023-02-15 11:41:47,041 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:41:47,041 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:41:47,046 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2023-02-15 11:41:47,246 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2023-02-15 11:41:47,246 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:41:47,246 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:41:47,246 INFO L85 PathProgramCache]: Analyzing trace with hash -1718599493, now seen corresponding path program 1 times [2023-02-15 11:41:47,246 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:41:47,246 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1188852443] [2023-02-15 11:41:47,246 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:47,247 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:41:47,252 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:41:47,252 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [748997508] [2023-02-15 11:41:47,252 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:41:47,252 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:41:47,252 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:41:47,253 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 11:41:47,255 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2023-02-15 11:41:47,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:41:47,308 INFO L263 TraceCheckSpWp]: Trace formula consists of 250 conjuncts, 50 conjunts are in the unsatisfiable core [2023-02-15 11:41:47,309 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:41:47,910 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 51 proven. 32 refuted. 0 times theorem prover too weak. 205 trivial. 0 not checked. [2023-02-15 11:41:47,910 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:41:49,144 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 51 proven. 23 refuted. 0 times theorem prover too weak. 214 trivial. 0 not checked. [2023-02-15 11:41:49,145 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:41:49,145 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1188852443] [2023-02-15 11:41:49,145 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:41:49,145 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [748997508] [2023-02-15 11:41:49,145 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [748997508] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 11:41:49,145 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 11:41:49,145 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 22 [2023-02-15 11:41:49,146 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1687079204] [2023-02-15 11:41:49,146 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 11:41:49,146 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-02-15 11:41:49,146 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:41:49,147 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-02-15 11:41:49,147 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=380, Unknown=0, NotChecked=0, Total=462 [2023-02-15 11:41:49,147 INFO L87 Difference]: Start difference. First operand 405 states and 534 transitions. Second operand has 22 states, 21 states have (on average 2.5238095238095237) internal successors, (53), 19 states have internal predecessors, (53), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2023-02-15 11:41:51,240 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 11:41:59,762 WARN L233 SmtUtils]: Spent 7.42s on a formula simplification that was a NOOP. DAG size: 70 (called from [L 361] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-02-15 11:42:08,480 WARN L233 SmtUtils]: Spent 6.68s on a formula simplification that was a NOOP. DAG size: 58 (called from [L 361] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-02-15 11:42:10,695 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 11:42:13,076 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 11:42:15,094 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 11:42:20,752 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 11:42:27,698 WARN L233 SmtUtils]: Spent 6.89s on a formula simplification that was a NOOP. DAG size: 55 (called from [L 361] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-02-15 11:42:35,023 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 11:42:37,025 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 11:42:39,030 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 11:42:40,612 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.44s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 11:42:45,090 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:42:45,090 INFO L93 Difference]: Finished difference Result 548 states and 758 transitions. [2023-02-15 11:42:45,091 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2023-02-15 11:42:45,091 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 2.5238095238095237) internal successors, (53), 19 states have internal predecessors, (53), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) Word has length 97 [2023-02-15 11:42:45,091 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:42:45,093 INFO L225 Difference]: With dead ends: 548 [2023-02-15 11:42:45,093 INFO L226 Difference]: Without dead ends: 546 [2023-02-15 11:42:45,094 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 213 GetRequests, 172 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 390 ImplicationChecksByTransitivity, 33.5s TimeCoverageRelationStatistics Valid=376, Invalid=1429, Unknown=1, NotChecked=0, Total=1806 [2023-02-15 11:42:45,094 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 145 mSDsluCounter, 287 mSDsCounter, 0 mSdLazyCounter, 1043 mSolverCounterSat, 146 mSolverCounterUnsat, 8 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 22.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 158 SdHoareTripleChecker+Valid, 331 SdHoareTripleChecker+Invalid, 1197 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 146 IncrementalHoareTripleChecker+Valid, 1043 IncrementalHoareTripleChecker+Invalid, 8 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 22.9s IncrementalHoareTripleChecker+Time [2023-02-15 11:42:45,094 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [158 Valid, 331 Invalid, 1197 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [146 Valid, 1043 Invalid, 8 Unknown, 0 Unchecked, 22.9s Time] [2023-02-15 11:42:45,095 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 546 states. [2023-02-15 11:42:45,177 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 546 to 468. [2023-02-15 11:42:45,178 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 468 states, 305 states have (on average 1.2524590163934426) internal successors, (382), 312 states have internal predecessors, (382), 127 states have call successors, (127), 35 states have call predecessors, (127), 35 states have return successors, (125), 120 states have call predecessors, (125), 125 states have call successors, (125) [2023-02-15 11:42:45,179 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 468 states to 468 states and 634 transitions. [2023-02-15 11:42:45,179 INFO L78 Accepts]: Start accepts. Automaton has 468 states and 634 transitions. Word has length 97 [2023-02-15 11:42:45,180 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:42:45,180 INFO L495 AbstractCegarLoop]: Abstraction has 468 states and 634 transitions. [2023-02-15 11:42:45,180 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 2.5238095238095237) internal successors, (53), 19 states have internal predecessors, (53), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2023-02-15 11:42:45,180 INFO L276 IsEmpty]: Start isEmpty. Operand 468 states and 634 transitions. [2023-02-15 11:42:45,181 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2023-02-15 11:42:45,181 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:42:45,181 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:42:45,188 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2023-02-15 11:42:45,385 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-02-15 11:42:45,386 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:42:45,386 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:42:45,386 INFO L85 PathProgramCache]: Analyzing trace with hash -245423741, now seen corresponding path program 1 times [2023-02-15 11:42:45,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:42:45,386 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1080083598] [2023-02-15 11:42:45,386 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:42:45,386 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:42:45,391 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:42:45,392 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1149179239] [2023-02-15 11:42:45,392 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:42:45,392 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:42:45,392 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:42:45,393 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 11:42:45,394 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2023-02-15 11:42:45,450 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:42:45,452 INFO L263 TraceCheckSpWp]: Trace formula consists of 308 conjuncts, 15 conjunts are in the unsatisfiable core [2023-02-15 11:42:45,453 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:42:45,564 INFO L134 CoverageAnalysis]: Checked inductivity of 357 backedges. 32 proven. 229 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2023-02-15 11:42:45,564 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:42:45,681 INFO L134 CoverageAnalysis]: Checked inductivity of 357 backedges. 32 proven. 37 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2023-02-15 11:42:45,681 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:42:45,681 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1080083598] [2023-02-15 11:42:45,681 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:42:45,681 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1149179239] [2023-02-15 11:42:45,681 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1149179239] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 11:42:45,681 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 11:42:45,681 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10] total 14 [2023-02-15 11:42:45,682 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1414131045] [2023-02-15 11:42:45,682 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 11:42:45,683 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-02-15 11:42:45,683 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:42:45,683 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-02-15 11:42:45,683 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2023-02-15 11:42:45,684 INFO L87 Difference]: Start difference. First operand 468 states and 634 transitions. Second operand has 14 states, 14 states have (on average 4.785714285714286) internal successors, (67), 14 states have internal predecessors, (67), 8 states have call successors, (33), 6 states have call predecessors, (33), 5 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) [2023-02-15 11:42:46,051 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:42:46,051 INFO L93 Difference]: Finished difference Result 1087 states and 1505 transitions. [2023-02-15 11:42:46,051 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-02-15 11:42:46,051 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.785714285714286) internal successors, (67), 14 states have internal predecessors, (67), 8 states have call successors, (33), 6 states have call predecessors, (33), 5 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) Word has length 112 [2023-02-15 11:42:46,052 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:42:46,054 INFO L225 Difference]: With dead ends: 1087 [2023-02-15 11:42:46,054 INFO L226 Difference]: Without dead ends: 883 [2023-02-15 11:42:46,055 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 230 GetRequests, 206 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=165, Invalid=297, Unknown=0, NotChecked=0, Total=462 [2023-02-15 11:42:46,055 INFO L413 NwaCegarLoop]: 72 mSDtfsCounter, 120 mSDsluCounter, 256 mSDsCounter, 0 mSdLazyCounter, 150 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 120 SdHoareTripleChecker+Valid, 328 SdHoareTripleChecker+Invalid, 188 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 150 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 11:42:46,056 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [120 Valid, 328 Invalid, 188 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 150 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 11:42:46,056 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2023-02-15 11:42:46,212 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 859. [2023-02-15 11:42:46,213 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 859 states, 549 states have (on average 1.2058287795992715) internal successors, (662), 560 states have internal predecessors, (662), 234 states have call successors, (234), 75 states have call predecessors, (234), 75 states have return successors, (229), 223 states have call predecessors, (229), 229 states have call successors, (229) [2023-02-15 11:42:46,219 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 859 states to 859 states and 1125 transitions. [2023-02-15 11:42:46,220 INFO L78 Accepts]: Start accepts. Automaton has 859 states and 1125 transitions. Word has length 112 [2023-02-15 11:42:46,220 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:42:46,220 INFO L495 AbstractCegarLoop]: Abstraction has 859 states and 1125 transitions. [2023-02-15 11:42:46,220 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.785714285714286) internal successors, (67), 14 states have internal predecessors, (67), 8 states have call successors, (33), 6 states have call predecessors, (33), 5 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) [2023-02-15 11:42:46,220 INFO L276 IsEmpty]: Start isEmpty. Operand 859 states and 1125 transitions. [2023-02-15 11:42:46,222 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 116 [2023-02-15 11:42:46,222 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:42:46,222 INFO L195 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:42:46,228 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2023-02-15 11:42:46,427 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2023-02-15 11:42:46,427 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:42:46,427 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:42:46,427 INFO L85 PathProgramCache]: Analyzing trace with hash -1897577373, now seen corresponding path program 2 times [2023-02-15 11:42:46,427 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:42:46,427 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1279783880] [2023-02-15 11:42:46,427 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:42:46,428 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:42:46,433 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:42:46,433 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [899693148] [2023-02-15 11:42:46,433 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-15 11:42:46,433 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:42:46,433 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:42:46,434 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 11:42:46,436 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2023-02-15 11:42:46,489 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-15 11:42:46,489 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 11:42:46,490 INFO L263 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 46 conjunts are in the unsatisfiable core [2023-02-15 11:42:46,492 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:42:46,972 INFO L134 CoverageAnalysis]: Checked inductivity of 455 backedges. 31 proven. 45 refuted. 0 times theorem prover too weak. 379 trivial. 0 not checked. [2023-02-15 11:42:46,972 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:42:48,406 INFO L134 CoverageAnalysis]: Checked inductivity of 455 backedges. 28 proven. 39 refuted. 0 times theorem prover too weak. 388 trivial. 0 not checked. [2023-02-15 11:42:48,407 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:42:48,407 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1279783880] [2023-02-15 11:42:48,407 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:42:48,407 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [899693148] [2023-02-15 11:42:48,407 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [899693148] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 11:42:48,407 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 11:42:48,407 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2023-02-15 11:42:48,407 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [701881352] [2023-02-15 11:42:48,407 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 11:42:48,407 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2023-02-15 11:42:48,407 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:42:48,411 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2023-02-15 11:42:48,411 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=424, Unknown=0, NotChecked=0, Total=506 [2023-02-15 11:42:48,412 INFO L87 Difference]: Start difference. First operand 859 states and 1125 transitions. Second operand has 23 states, 23 states have (on average 2.347826086956522) internal successors, (54), 20 states have internal predecessors, (54), 11 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (35), 12 states have call predecessors, (35), 11 states have call successors, (35) [2023-02-15 11:43:08,891 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:43:08,891 INFO L93 Difference]: Finished difference Result 1105 states and 1492 transitions. [2023-02-15 11:43:08,892 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2023-02-15 11:43:08,892 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.347826086956522) internal successors, (54), 20 states have internal predecessors, (54), 11 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (35), 12 states have call predecessors, (35), 11 states have call successors, (35) Word has length 115 [2023-02-15 11:43:08,892 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:43:08,896 INFO L225 Difference]: With dead ends: 1105 [2023-02-15 11:43:08,896 INFO L226 Difference]: Without dead ends: 1103 [2023-02-15 11:43:08,897 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 262 GetRequests, 207 SyntacticMatches, 0 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 822 ImplicationChecksByTransitivity, 11.7s TimeCoverageRelationStatistics Valid=651, Invalid=2541, Unknown=0, NotChecked=0, Total=3192 [2023-02-15 11:43:08,897 INFO L413 NwaCegarLoop]: 113 mSDtfsCounter, 190 mSDsluCounter, 606 mSDsCounter, 0 mSdLazyCounter, 1404 mSolverCounterSat, 292 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 194 SdHoareTripleChecker+Valid, 719 SdHoareTripleChecker+Invalid, 1696 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 292 IncrementalHoareTripleChecker+Valid, 1404 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.0s IncrementalHoareTripleChecker+Time [2023-02-15 11:43:08,897 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [194 Valid, 719 Invalid, 1696 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [292 Valid, 1404 Invalid, 0 Unknown, 0 Unchecked, 9.0s Time] [2023-02-15 11:43:08,898 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1103 states. [2023-02-15 11:43:09,163 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1103 to 1050. [2023-02-15 11:43:09,164 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1050 states, 663 states have (on average 1.2292609351432882) internal successors, (815), 674 states have internal predecessors, (815), 302 states have call successors, (302), 84 states have call predecessors, (302), 84 states have return successors, (297), 291 states have call predecessors, (297), 297 states have call successors, (297) [2023-02-15 11:43:09,167 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1050 states to 1050 states and 1414 transitions. [2023-02-15 11:43:09,167 INFO L78 Accepts]: Start accepts. Automaton has 1050 states and 1414 transitions. Word has length 115 [2023-02-15 11:43:09,169 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:43:09,169 INFO L495 AbstractCegarLoop]: Abstraction has 1050 states and 1414 transitions. [2023-02-15 11:43:09,169 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.347826086956522) internal successors, (54), 20 states have internal predecessors, (54), 11 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (35), 12 states have call predecessors, (35), 11 states have call successors, (35) [2023-02-15 11:43:09,169 INFO L276 IsEmpty]: Start isEmpty. Operand 1050 states and 1414 transitions. [2023-02-15 11:43:09,170 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2023-02-15 11:43:09,170 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:43:09,170 INFO L195 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:43:09,189 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2023-02-15 11:43:09,375 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:43:09,375 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:43:09,375 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:43:09,375 INFO L85 PathProgramCache]: Analyzing trace with hash 364386885, now seen corresponding path program 3 times [2023-02-15 11:43:09,375 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:43:09,375 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1019511819] [2023-02-15 11:43:09,375 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:43:09,375 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:43:09,381 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:43:09,381 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1343209831] [2023-02-15 11:43:09,381 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-15 11:43:09,381 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:43:09,381 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:43:09,382 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 11:43:09,384 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2023-02-15 11:43:09,435 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-02-15 11:43:09,435 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 11:43:09,437 INFO L263 TraceCheckSpWp]: Trace formula consists of 226 conjuncts, 70 conjunts are in the unsatisfiable core [2023-02-15 11:43:09,439 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:43:10,035 INFO L134 CoverageAnalysis]: Checked inductivity of 462 backedges. 75 proven. 47 refuted. 0 times theorem prover too weak. 340 trivial. 0 not checked. [2023-02-15 11:43:10,035 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:43:11,112 INFO L134 CoverageAnalysis]: Checked inductivity of 462 backedges. 70 proven. 43 refuted. 0 times theorem prover too weak. 349 trivial. 0 not checked. [2023-02-15 11:43:11,112 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:43:11,112 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1019511819] [2023-02-15 11:43:11,112 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:43:11,112 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1343209831] [2023-02-15 11:43:11,112 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1343209831] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 11:43:11,112 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 11:43:11,112 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 14] total 28 [2023-02-15 11:43:11,112 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [192486326] [2023-02-15 11:43:11,112 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 11:43:11,112 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-02-15 11:43:11,113 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:43:11,113 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-02-15 11:43:11,113 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=132, Invalid=624, Unknown=0, NotChecked=0, Total=756 [2023-02-15 11:43:11,113 INFO L87 Difference]: Start difference. First operand 1050 states and 1414 transitions. Second operand has 28 states, 26 states have (on average 2.576923076923077) internal successors, (67), 25 states have internal predecessors, (67), 13 states have call successors, (36), 3 states have call predecessors, (36), 3 states have return successors, (34), 13 states have call predecessors, (34), 11 states have call successors, (34) [2023-02-15 11:43:18,071 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:43:18,072 INFO L93 Difference]: Finished difference Result 1378 states and 1876 transitions. [2023-02-15 11:43:18,072 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2023-02-15 11:43:18,072 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 26 states have (on average 2.576923076923077) internal successors, (67), 25 states have internal predecessors, (67), 13 states have call successors, (36), 3 states have call predecessors, (36), 3 states have return successors, (34), 13 states have call predecessors, (34), 11 states have call successors, (34) Word has length 119 [2023-02-15 11:43:18,073 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:43:18,076 INFO L225 Difference]: With dead ends: 1378 [2023-02-15 11:43:18,077 INFO L226 Difference]: Without dead ends: 1374 [2023-02-15 11:43:18,078 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 265 GetRequests, 210 SyntacticMatches, 0 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 704 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=642, Invalid=2550, Unknown=0, NotChecked=0, Total=3192 [2023-02-15 11:43:18,078 INFO L413 NwaCegarLoop]: 51 mSDtfsCounter, 193 mSDsluCounter, 347 mSDsCounter, 0 mSdLazyCounter, 1156 mSolverCounterSat, 242 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 194 SdHoareTripleChecker+Valid, 398 SdHoareTripleChecker+Invalid, 1398 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 242 IncrementalHoareTripleChecker+Valid, 1156 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.8s IncrementalHoareTripleChecker+Time [2023-02-15 11:43:18,078 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [194 Valid, 398 Invalid, 1398 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [242 Valid, 1156 Invalid, 0 Unknown, 0 Unchecked, 4.8s Time] [2023-02-15 11:43:18,079 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1374 states. [2023-02-15 11:43:18,404 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1374 to 1241. [2023-02-15 11:43:18,406 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1241 states, 791 states have (on average 1.2402022756005058) internal successors, (981), 803 states have internal predecessors, (981), 349 states have call successors, (349), 101 states have call predecessors, (349), 100 states have return successors, (344), 336 states have call predecessors, (344), 344 states have call successors, (344) [2023-02-15 11:43:18,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1241 states to 1241 states and 1674 transitions. [2023-02-15 11:43:18,409 INFO L78 Accepts]: Start accepts. Automaton has 1241 states and 1674 transitions. Word has length 119 [2023-02-15 11:43:18,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:43:18,409 INFO L495 AbstractCegarLoop]: Abstraction has 1241 states and 1674 transitions. [2023-02-15 11:43:18,409 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 26 states have (on average 2.576923076923077) internal successors, (67), 25 states have internal predecessors, (67), 13 states have call successors, (36), 3 states have call predecessors, (36), 3 states have return successors, (34), 13 states have call predecessors, (34), 11 states have call successors, (34) [2023-02-15 11:43:18,409 INFO L276 IsEmpty]: Start isEmpty. Operand 1241 states and 1674 transitions. [2023-02-15 11:43:18,410 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2023-02-15 11:43:18,411 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:43:18,411 INFO L195 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:43:18,415 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2023-02-15 11:43:18,615 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:43:18,615 INFO L420 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:43:18,616 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:43:18,616 INFO L85 PathProgramCache]: Analyzing trace with hash -1036292276, now seen corresponding path program 1 times [2023-02-15 11:43:18,616 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:43:18,616 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1401979863] [2023-02-15 11:43:18,616 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:43:18,616 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:43:18,622 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:43:18,622 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1422673697] [2023-02-15 11:43:18,622 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:43:18,622 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:43:18,622 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:43:18,623 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 11:43:18,625 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2023-02-15 11:43:18,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 11:43:18,677 INFO L263 TraceCheckSpWp]: Trace formula consists of 325 conjuncts, 15 conjunts are in the unsatisfiable core [2023-02-15 11:43:18,679 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:43:18,801 INFO L134 CoverageAnalysis]: Checked inductivity of 586 backedges. 32 proven. 434 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2023-02-15 11:43:18,801 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:43:18,903 INFO L134 CoverageAnalysis]: Checked inductivity of 586 backedges. 32 proven. 50 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2023-02-15 11:43:18,903 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:43:18,903 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1401979863] [2023-02-15 11:43:18,903 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:43:18,903 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1422673697] [2023-02-15 11:43:18,903 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1422673697] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 11:43:18,903 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 11:43:18,903 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10] total 14 [2023-02-15 11:43:18,904 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [457477991] [2023-02-15 11:43:18,904 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 11:43:18,904 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-02-15 11:43:18,904 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:43:18,904 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-02-15 11:43:18,905 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2023-02-15 11:43:18,905 INFO L87 Difference]: Start difference. First operand 1241 states and 1674 transitions. Second operand has 14 states, 14 states have (on average 5.142857142857143) internal successors, (72), 14 states have internal predecessors, (72), 10 states have call successors, (41), 7 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) [2023-02-15 11:43:19,421 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:43:19,421 INFO L93 Difference]: Finished difference Result 1291 states and 1728 transitions. [2023-02-15 11:43:19,422 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-02-15 11:43:19,422 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 5.142857142857143) internal successors, (72), 14 states have internal predecessors, (72), 10 states have call successors, (41), 7 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) Word has length 129 [2023-02-15 11:43:19,422 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:43:19,425 INFO L225 Difference]: With dead ends: 1291 [2023-02-15 11:43:19,426 INFO L226 Difference]: Without dead ends: 1271 [2023-02-15 11:43:19,426 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 264 GetRequests, 240 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=166, Invalid=296, Unknown=0, NotChecked=0, Total=462 [2023-02-15 11:43:19,426 INFO L413 NwaCegarLoop]: 70 mSDtfsCounter, 93 mSDsluCounter, 165 mSDsCounter, 0 mSdLazyCounter, 116 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 93 SdHoareTripleChecker+Valid, 235 SdHoareTripleChecker+Invalid, 139 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 116 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 11:43:19,427 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [93 Valid, 235 Invalid, 139 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 116 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 11:43:19,427 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1271 states. [2023-02-15 11:43:19,747 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1271 to 1265. [2023-02-15 11:43:19,749 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1265 states, 815 states have (on average 1.2184049079754602) internal successors, (993), 827 states have internal predecessors, (993), 349 states have call successors, (349), 101 states have call predecessors, (349), 100 states have return successors, (344), 336 states have call predecessors, (344), 344 states have call successors, (344) [2023-02-15 11:43:19,753 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1265 states to 1265 states and 1686 transitions. [2023-02-15 11:43:19,754 INFO L78 Accepts]: Start accepts. Automaton has 1265 states and 1686 transitions. Word has length 129 [2023-02-15 11:43:19,754 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:43:19,754 INFO L495 AbstractCegarLoop]: Abstraction has 1265 states and 1686 transitions. [2023-02-15 11:43:19,754 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 5.142857142857143) internal successors, (72), 14 states have internal predecessors, (72), 10 states have call successors, (41), 7 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) [2023-02-15 11:43:19,754 INFO L276 IsEmpty]: Start isEmpty. Operand 1265 states and 1686 transitions. [2023-02-15 11:43:19,759 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2023-02-15 11:43:19,759 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:43:19,759 INFO L195 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:43:19,766 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2023-02-15 11:43:19,964 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:43:19,964 INFO L420 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:43:19,965 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:43:19,965 INFO L85 PathProgramCache]: Analyzing trace with hash -2066876172, now seen corresponding path program 2 times [2023-02-15 11:43:19,965 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:43:19,965 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1246989840] [2023-02-15 11:43:19,965 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:43:19,965 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:43:19,972 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:43:19,972 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [350311125] [2023-02-15 11:43:19,972 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-15 11:43:19,972 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:43:19,972 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:43:19,978 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 11:43:19,980 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2023-02-15 11:43:20,049 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-15 11:43:20,049 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 11:43:20,051 INFO L263 TraceCheckSpWp]: Trace formula consists of 327 conjuncts, 65 conjunts are in the unsatisfiable core [2023-02-15 11:43:20,053 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:43:20,687 INFO L134 CoverageAnalysis]: Checked inductivity of 588 backedges. 35 proven. 58 refuted. 0 times theorem prover too weak. 495 trivial. 0 not checked. [2023-02-15 11:43:20,688 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 11:43:25,594 INFO L134 CoverageAnalysis]: Checked inductivity of 588 backedges. 32 proven. 52 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2023-02-15 11:43:25,594 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 11:43:25,594 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1246989840] [2023-02-15 11:43:25,595 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 11:43:25,595 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [350311125] [2023-02-15 11:43:25,595 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [350311125] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 11:43:25,595 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 11:43:25,595 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 13] total 28 [2023-02-15 11:43:25,595 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1364931781] [2023-02-15 11:43:25,595 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 11:43:25,595 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-02-15 11:43:25,595 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 11:43:25,596 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-02-15 11:43:25,596 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=647, Unknown=0, NotChecked=0, Total=756 [2023-02-15 11:43:25,596 INFO L87 Difference]: Start difference. First operand 1265 states and 1686 transitions. Second operand has 28 states, 26 states have (on average 2.4615384615384617) internal successors, (64), 25 states have internal predecessors, (64), 13 states have call successors, (40), 3 states have call predecessors, (40), 2 states have return successors, (39), 12 states have call predecessors, (39), 11 states have call successors, (39) [2023-02-15 11:43:49,952 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 11:44:24,703 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 11:44:24,703 INFO L93 Difference]: Finished difference Result 1613 states and 2211 transitions. [2023-02-15 11:44:24,705 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 64 states. [2023-02-15 11:44:24,705 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 26 states have (on average 2.4615384615384617) internal successors, (64), 25 states have internal predecessors, (64), 13 states have call successors, (40), 3 states have call predecessors, (40), 2 states have return successors, (39), 12 states have call predecessors, (39), 11 states have call successors, (39) Word has length 130 [2023-02-15 11:44:24,706 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 11:44:24,710 INFO L225 Difference]: With dead ends: 1613 [2023-02-15 11:44:24,710 INFO L226 Difference]: Without dead ends: 1593 [2023-02-15 11:44:24,712 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 314 GetRequests, 231 SyntacticMatches, 1 SemanticMatches, 82 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2030 ImplicationChecksByTransitivity, 30.9s TimeCoverageRelationStatistics Valid=1270, Invalid=5702, Unknown=0, NotChecked=0, Total=6972 [2023-02-15 11:44:24,713 INFO L413 NwaCegarLoop]: 159 mSDtfsCounter, 383 mSDsluCounter, 1164 mSDsCounter, 0 mSdLazyCounter, 2185 mSolverCounterSat, 588 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 30.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 391 SdHoareTripleChecker+Valid, 1323 SdHoareTripleChecker+Invalid, 2774 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 588 IncrementalHoareTripleChecker+Valid, 2185 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 31.0s IncrementalHoareTripleChecker+Time [2023-02-15 11:44:24,713 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [391 Valid, 1323 Invalid, 2774 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [588 Valid, 2185 Invalid, 1 Unknown, 0 Unchecked, 31.0s Time] [2023-02-15 11:44:24,714 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1593 states. [2023-02-15 11:44:25,179 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1593 to 1413. [2023-02-15 11:44:25,180 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1413 states, 906 states have (on average 1.2273730684326711) internal successors, (1112), 917 states have internal predecessors, (1112), 397 states have call successors, (397), 110 states have call predecessors, (397), 109 states have return successors, (392), 385 states have call predecessors, (392), 392 states have call successors, (392) [2023-02-15 11:44:25,183 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1413 states to 1413 states and 1901 transitions. [2023-02-15 11:44:25,184 INFO L78 Accepts]: Start accepts. Automaton has 1413 states and 1901 transitions. Word has length 130 [2023-02-15 11:44:25,184 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 11:44:25,184 INFO L495 AbstractCegarLoop]: Abstraction has 1413 states and 1901 transitions. [2023-02-15 11:44:25,184 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 26 states have (on average 2.4615384615384617) internal successors, (64), 25 states have internal predecessors, (64), 13 states have call successors, (40), 3 states have call predecessors, (40), 2 states have return successors, (39), 12 states have call predecessors, (39), 11 states have call successors, (39) [2023-02-15 11:44:25,184 INFO L276 IsEmpty]: Start isEmpty. Operand 1413 states and 1901 transitions. [2023-02-15 11:44:25,185 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 148 [2023-02-15 11:44:25,185 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 11:44:25,185 INFO L195 NwaCegarLoop]: trace histogram [20, 19, 19, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 11:44:25,190 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Ended with exit code 0 [2023-02-15 11:44:25,390 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,23 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:44:25,390 INFO L420 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 11:44:25,390 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 11:44:25,390 INFO L85 PathProgramCache]: Analyzing trace with hash -1962327715, now seen corresponding path program 4 times [2023-02-15 11:44:25,390 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 11:44:25,390 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [404869797] [2023-02-15 11:44:25,390 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 11:44:25,390 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 11:44:25,396 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 11:44:25,396 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1913107607] [2023-02-15 11:44:25,396 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-02-15 11:44:25,396 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 11:44:25,396 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 11:44:25,397 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 11:44:25,399 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Waiting until timeout for monitored process [2023-02-15 11:44:25,463 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-02-15 11:44:25,464 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 11:44:25,465 INFO L263 TraceCheckSpWp]: Trace formula consists of 325 conjuncts, 86 conjunts are in the unsatisfiable core [2023-02-15 11:44:25,472 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 11:44:27,786 INFO L134 CoverageAnalysis]: Checked inductivity of 822 backedges. 176 proven. 91 refuted. 0 times theorem prover too weak. 555 trivial. 0 not checked. [2023-02-15 11:44:27,786 INFO L328 TraceCheckSpWp]: Computing backward predicates...