./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version b5317dae 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/fermat1-ll_unwindbound100.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 ac7d6bbeae1af74610eb5ea0ec9cc56676532539c7535ebfdf72e0c17174815d --- Real Ultimate output --- This is Ultimate 0.2.2-?-b5317da-m [2023-02-16 02:07:08,111 INFO L177 SettingsManager]: Resetting all preferences to default values... [2023-02-16 02:07:08,113 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2023-02-16 02:07:08,143 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2023-02-16 02:07:08,144 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2023-02-16 02:07:08,146 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2023-02-16 02:07:08,148 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2023-02-16 02:07:08,150 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2023-02-16 02:07:08,152 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2023-02-16 02:07:08,156 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2023-02-16 02:07:08,157 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2023-02-16 02:07:08,159 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2023-02-16 02:07:08,160 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2023-02-16 02:07:08,162 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2023-02-16 02:07:08,163 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2023-02-16 02:07:08,165 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2023-02-16 02:07:08,165 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2023-02-16 02:07:08,167 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2023-02-16 02:07:08,168 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2023-02-16 02:07:08,173 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2023-02-16 02:07:08,174 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2023-02-16 02:07:08,175 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2023-02-16 02:07:08,176 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2023-02-16 02:07:08,176 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2023-02-16 02:07:08,184 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2023-02-16 02:07:08,184 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2023-02-16 02:07:08,184 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2023-02-16 02:07:08,186 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2023-02-16 02:07:08,186 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2023-02-16 02:07:08,188 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2023-02-16 02:07:08,188 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2023-02-16 02:07:08,189 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2023-02-16 02:07:08,191 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2023-02-16 02:07:08,191 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2023-02-16 02:07:08,192 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2023-02-16 02:07:08,193 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2023-02-16 02:07:08,193 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2023-02-16 02:07:08,193 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2023-02-16 02:07:08,193 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2023-02-16 02:07:08,195 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2023-02-16 02:07:08,195 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2023-02-16 02:07:08,207 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2023-02-16 02:07:08,254 INFO L113 SettingsManager]: Loading preferences was successful [2023-02-16 02:07:08,254 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2023-02-16 02:07:08,255 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-02-16 02:07:08,255 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-02-16 02:07:08,256 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-02-16 02:07:08,256 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-02-16 02:07:08,256 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-02-16 02:07:08,257 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2023-02-16 02:07:08,257 INFO L138 SettingsManager]: * Use SBE=true [2023-02-16 02:07:08,257 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-02-16 02:07:08,258 INFO L138 SettingsManager]: * sizeof long=4 [2023-02-16 02:07:08,258 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2023-02-16 02:07:08,258 INFO L138 SettingsManager]: * sizeof POINTER=4 [2023-02-16 02:07:08,258 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2023-02-16 02:07:08,258 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-02-16 02:07:08,259 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-02-16 02:07:08,259 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-02-16 02:07:08,259 INFO L138 SettingsManager]: * sizeof long double=12 [2023-02-16 02:07:08,259 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2023-02-16 02:07:08,259 INFO L138 SettingsManager]: * Use constant arrays=true [2023-02-16 02:07:08,259 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-02-16 02:07:08,260 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-02-16 02:07:08,260 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-02-16 02:07:08,260 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2023-02-16 02:07:08,260 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-02-16 02:07:08,261 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-02-16 02:07:08,261 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-02-16 02:07:08,261 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-02-16 02:07:08,261 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2023-02-16 02:07:08,261 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-02-16 02:07:08,262 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-02-16 02:07:08,262 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-02-16 02:07:08,262 INFO L138 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-02-16 02:07:08,262 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-02-16 02:07:08,262 INFO L138 SettingsManager]: * Independence relation used for large block encoding in concurrent analysis=SYNTACTIC [2023-02-16 02:07:08,262 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 -> ac7d6bbeae1af74610eb5ea0ec9cc56676532539c7535ebfdf72e0c17174815d [2023-02-16 02:07:08,465 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-02-16 02:07:08,484 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-02-16 02:07:08,487 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-02-16 02:07:08,488 INFO L271 PluginConnector]: Initializing CDTParser... [2023-02-16 02:07:08,488 INFO L275 PluginConnector]: CDTParser initialized [2023-02-16 02:07:08,489 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c [2023-02-16 02:07:09,589 INFO L500 CDTParser]: Created temporary CDT project at NULL [2023-02-16 02:07:09,748 INFO L351 CDTParser]: Found 1 translation units. [2023-02-16 02:07:09,749 INFO L172 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c [2023-02-16 02:07:09,757 INFO L394 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c120b0260/78d7c9cb52cc48bf85ffd2691da3c6a6/FLAG18d303502 [2023-02-16 02:07:10,156 INFO L402 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c120b0260/78d7c9cb52cc48bf85ffd2691da3c6a6 [2023-02-16 02:07:10,158 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-02-16 02:07:10,160 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2023-02-16 02:07:10,163 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-02-16 02:07:10,163 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-02-16 02:07:10,166 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2023-02-16 02:07:10,166 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.02 02:07:10" (1/1) ... [2023-02-16 02:07:10,167 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@48f7a6d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10, skipping insertion in model container [2023-02-16 02:07:10,167 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.02 02:07:10" (1/1) ... [2023-02-16 02:07:10,173 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2023-02-16 02:07:10,191 INFO L178 MainTranslator]: Built tables and reachable declarations [2023-02-16 02:07:10,338 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/fermat1-ll_unwindbound100.c[535,548] [2023-02-16 02:07:10,365 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-16 02:07:10,376 INFO L203 MainTranslator]: Completed pre-run [2023-02-16 02:07:10,390 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/fermat1-ll_unwindbound100.c[535,548] [2023-02-16 02:07:10,413 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-16 02:07:10,429 INFO L208 MainTranslator]: Completed translation [2023-02-16 02:07:10,431 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10 WrapperNode [2023-02-16 02:07:10,432 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-02-16 02:07:10,433 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-02-16 02:07:10,433 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-02-16 02:07:10,433 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2023-02-16 02:07:10,439 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10" (1/1) ... [2023-02-16 02:07:10,452 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10" (1/1) ... [2023-02-16 02:07:10,470 INFO L138 Inliner]: procedures = 14, calls = 13, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 67 [2023-02-16 02:07:10,471 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-02-16 02:07:10,472 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-02-16 02:07:10,472 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2023-02-16 02:07:10,472 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2023-02-16 02:07:10,479 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10" (1/1) ... [2023-02-16 02:07:10,480 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10" (1/1) ... [2023-02-16 02:07:10,483 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10" (1/1) ... [2023-02-16 02:07:10,483 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10" (1/1) ... [2023-02-16 02:07:10,496 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10" (1/1) ... [2023-02-16 02:07:10,499 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10" (1/1) ... [2023-02-16 02:07:10,506 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10" (1/1) ... [2023-02-16 02:07:10,507 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10" (1/1) ... [2023-02-16 02:07:10,509 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-02-16 02:07:10,510 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-02-16 02:07:10,511 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2023-02-16 02:07:10,511 INFO L275 PluginConnector]: RCFGBuilder initialized [2023-02-16 02:07:10,513 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10" (1/1) ... [2023-02-16 02:07:10,518 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-02-16 02:07:10,527 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:10,549 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-16 02:07:10,569 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-16 02:07:10,585 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-02-16 02:07:10,585 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-02-16 02:07:10,585 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-02-16 02:07:10,585 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-02-16 02:07:10,585 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-02-16 02:07:10,586 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-02-16 02:07:10,586 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-02-16 02:07:10,586 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-02-16 02:07:10,644 INFO L235 CfgBuilder]: Building ICFG [2023-02-16 02:07:10,647 INFO L261 CfgBuilder]: Building CFG for each procedure with an implementation [2023-02-16 02:07:10,774 INFO L276 CfgBuilder]: Performing block encoding [2023-02-16 02:07:10,783 INFO L295 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-02-16 02:07:10,784 INFO L300 CfgBuilder]: Removed 3 assume(true) statements. [2023-02-16 02:07:10,786 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.02 02:07:10 BoogieIcfgContainer [2023-02-16 02:07:10,786 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-02-16 02:07:10,788 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-02-16 02:07:10,788 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2023-02-16 02:07:10,791 INFO L275 PluginConnector]: TraceAbstraction initialized [2023-02-16 02:07:10,792 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.02 02:07:10" (1/3) ... [2023-02-16 02:07:10,792 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2a7c8b40 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.02 02:07:10, skipping insertion in model container [2023-02-16 02:07:10,792 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 02:07:10" (2/3) ... [2023-02-16 02:07:10,793 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2a7c8b40 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.02 02:07:10, skipping insertion in model container [2023-02-16 02:07:10,793 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.02 02:07:10" (3/3) ... [2023-02-16 02:07:10,794 INFO L112 eAbstractionObserver]: Analyzing ICFG fermat1-ll_unwindbound100.c [2023-02-16 02:07:10,809 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-02-16 02:07:10,809 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-02-16 02:07:10,844 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-02-16 02:07:10,849 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;@41da32d2, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-02-16 02:07:10,849 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-02-16 02:07:10,852 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-02-16 02:07:10,857 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2023-02-16 02:07:10,858 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:10,858 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:10,858 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:10,862 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:10,862 INFO L85 PathProgramCache]: Analyzing trace with hash 738208203, now seen corresponding path program 1 times [2023-02-16 02:07:10,869 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:10,869 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1438906091] [2023-02-16 02:07:10,870 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:10,870 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:10,961 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:10,961 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1836955133] [2023-02-16 02:07:10,962 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:10,962 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:10,962 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:10,964 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-16 02:07:10,965 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-16 02:07:11,036 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:11,038 INFO L263 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 1 conjunts are in the unsatisfiable core [2023-02-16 02:07:11,041 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:11,072 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-02-16 02:07:11,072 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-16 02:07:11,072 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:11,083 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1438906091] [2023-02-16 02:07:11,083 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:11,083 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1836955133] [2023-02-16 02:07:11,084 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1836955133] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-16 02:07:11,084 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-16 02:07:11,085 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-02-16 02:07:11,098 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [931917697] [2023-02-16 02:07:11,099 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 02:07:11,105 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-02-16 02:07:11,106 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:11,131 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-02-16 02:07:11,132 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-02-16 02:07:11,134 INFO L87 Difference]: Start difference. First operand has 32 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2023-02-16 02:07:11,153 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:11,154 INFO L93 Difference]: Finished difference Result 61 states and 94 transitions. [2023-02-16 02:07:11,154 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-02-16 02:07:11,155 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2023-02-16 02:07:11,156 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:11,160 INFO L225 Difference]: With dead ends: 61 [2023-02-16 02:07:11,160 INFO L226 Difference]: Without dead ends: 28 [2023-02-16 02:07:11,163 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 17 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-16 02:07:11,166 INFO L413 NwaCegarLoop]: 41 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, 41 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-16 02:07:11,167 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-16 02:07:11,181 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2023-02-16 02:07:11,194 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2023-02-16 02:07:11,195 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 19 states have (on average 1.368421052631579) internal successors, (26), 20 states have internal predecessors, (26), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-02-16 02:07:11,197 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2023-02-16 02:07:11,199 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 18 [2023-02-16 02:07:11,199 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:11,199 INFO L495 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2023-02-16 02:07:11,200 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2023-02-16 02:07:11,201 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2023-02-16 02:07:11,203 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2023-02-16 02:07:11,203 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:11,203 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:11,209 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-02-16 02:07:11,409 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-16 02:07:11,410 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:11,410 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:11,411 INFO L85 PathProgramCache]: Analyzing trace with hash -1770759922, now seen corresponding path program 1 times [2023-02-16 02:07:11,411 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:11,411 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1510389666] [2023-02-16 02:07:11,411 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:11,411 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:11,436 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:11,440 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [524982634] [2023-02-16 02:07:11,441 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:11,441 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:11,441 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:11,465 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-16 02:07:11,467 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-16 02:07:11,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:11,534 INFO L263 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 3 conjunts are in the unsatisfiable core [2023-02-16 02:07:11,536 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:11,608 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-02-16 02:07:11,608 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-16 02:07:11,608 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:11,608 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1510389666] [2023-02-16 02:07:11,608 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:11,609 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [524982634] [2023-02-16 02:07:11,609 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [524982634] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-16 02:07:11,609 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-16 02:07:11,609 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-02-16 02:07:11,609 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [549475444] [2023-02-16 02:07:11,609 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 02:07:11,610 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-02-16 02:07:11,610 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:11,611 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-02-16 02:07:11,612 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-02-16 02:07:11,613 INFO L87 Difference]: Start difference. First operand 28 states and 37 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-02-16 02:07:11,641 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:11,641 INFO L93 Difference]: Finished difference Result 37 states and 46 transitions. [2023-02-16 02:07:11,641 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-02-16 02:07:11,642 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2023-02-16 02:07:11,642 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:11,642 INFO L225 Difference]: With dead ends: 37 [2023-02-16 02:07:11,642 INFO L226 Difference]: Without dead ends: 30 [2023-02-16 02:07:11,643 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 16 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-16 02:07:11,644 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 0 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:11,644 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 91 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-16 02:07:11,646 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2023-02-16 02:07:11,650 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2023-02-16 02:07:11,650 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 21 states have (on average 1.3333333333333333) internal successors, (28), 22 states have internal predecessors, (28), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-02-16 02:07:11,651 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2023-02-16 02:07:11,651 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 19 [2023-02-16 02:07:11,652 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:11,652 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2023-02-16 02:07:11,652 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-02-16 02:07:11,652 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2023-02-16 02:07:11,653 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2023-02-16 02:07:11,653 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:11,653 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:11,661 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-16 02:07:11,853 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-16 02:07:11,854 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:11,855 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:11,855 INFO L85 PathProgramCache]: Analyzing trace with hash -1769091626, now seen corresponding path program 1 times [2023-02-16 02:07:11,855 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:11,855 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1714412887] [2023-02-16 02:07:11,855 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:11,856 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:11,868 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:11,868 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1716427633] [2023-02-16 02:07:11,868 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:11,868 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:11,868 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:11,870 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-16 02:07:11,870 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-16 02:07:11,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:11,915 INFO L263 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 12 conjunts are in the unsatisfiable core [2023-02-16 02:07:11,917 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:11,993 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-02-16 02:07:11,993 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-16 02:07:11,994 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:11,994 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1714412887] [2023-02-16 02:07:11,994 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:11,994 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1716427633] [2023-02-16 02:07:11,994 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1716427633] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-16 02:07:11,995 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-16 02:07:11,995 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-02-16 02:07:11,995 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1567625314] [2023-02-16 02:07:11,995 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 02:07:11,996 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-16 02:07:11,996 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:11,996 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-16 02:07:11,997 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-02-16 02:07:11,997 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-02-16 02:07:14,140 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-16 02:07:15,922 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.03s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-16 02:07:17,433 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.49s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-16 02:07:17,444 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:17,444 INFO L93 Difference]: Finished difference Result 49 states and 66 transitions. [2023-02-16 02:07:17,445 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-02-16 02:07:17,445 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2023-02-16 02:07:17,445 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:17,446 INFO L225 Difference]: With dead ends: 49 [2023-02-16 02:07:17,446 INFO L226 Difference]: Without dead ends: 47 [2023-02-16 02:07:17,447 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-02-16 02:07:17,447 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 16 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 2 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 56 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.4s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:17,448 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 103 Invalid, 56 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 53 Invalid, 1 Unknown, 0 Unchecked, 5.4s Time] [2023-02-16 02:07:17,448 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-02-16 02:07:17,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2023-02-16 02:07:17,465 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 33 states have (on average 1.393939393939394) internal successors, (46), 34 states have internal predecessors, (46), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2023-02-16 02:07:17,469 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 63 transitions. [2023-02-16 02:07:17,472 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 63 transitions. Word has length 19 [2023-02-16 02:07:17,473 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:17,473 INFO L495 AbstractCegarLoop]: Abstraction has 46 states and 63 transitions. [2023-02-16 02:07:17,473 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-02-16 02:07:17,474 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 63 transitions. [2023-02-16 02:07:17,475 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2023-02-16 02:07:17,475 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:17,475 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:17,484 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-16 02:07:17,680 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-16 02:07:17,681 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:17,681 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:17,682 INFO L85 PathProgramCache]: Analyzing trace with hash -82041861, now seen corresponding path program 1 times [2023-02-16 02:07:17,682 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:17,682 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1389116323] [2023-02-16 02:07:17,682 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:17,682 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:17,698 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:17,699 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1176119502] [2023-02-16 02:07:17,699 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:17,699 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:17,699 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:17,700 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-16 02:07:17,722 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-16 02:07:17,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:17,749 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 13 conjunts are in the unsatisfiable core [2023-02-16 02:07:17,751 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:17,834 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-02-16 02:07:17,835 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 02:07:17,956 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-02-16 02:07:17,956 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:17,956 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1389116323] [2023-02-16 02:07:17,956 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:17,957 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1176119502] [2023-02-16 02:07:17,957 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1176119502] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 02:07:17,957 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 02:07:17,957 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 11 [2023-02-16 02:07:17,957 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2130114647] [2023-02-16 02:07:17,958 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 02:07:17,958 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-02-16 02:07:17,958 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:17,959 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-02-16 02:07:17,959 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2023-02-16 02:07:17,959 INFO L87 Difference]: Start difference. First operand 46 states and 63 transitions. Second operand has 11 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) [2023-02-16 02:07:18,094 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:18,095 INFO L93 Difference]: Finished difference Result 53 states and 69 transitions. [2023-02-16 02:07:18,095 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-02-16 02:07:18,095 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) Word has length 25 [2023-02-16 02:07:18,096 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:18,101 INFO L225 Difference]: With dead ends: 53 [2023-02-16 02:07:18,102 INFO L226 Difference]: Without dead ends: 48 [2023-02-16 02:07:18,103 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 38 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=136, Unknown=0, NotChecked=0, Total=182 [2023-02-16 02:07:18,105 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 28 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 119 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:18,106 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 139 Invalid, 119 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-16 02:07:18,110 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2023-02-16 02:07:18,130 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2023-02-16 02:07:18,130 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 35 states have (on average 1.2857142857142858) internal successors, (45), 35 states have internal predecessors, (45), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2023-02-16 02:07:18,133 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 62 transitions. [2023-02-16 02:07:18,133 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 62 transitions. Word has length 25 [2023-02-16 02:07:18,134 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:18,134 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 62 transitions. [2023-02-16 02:07:18,134 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) [2023-02-16 02:07:18,134 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 62 transitions. [2023-02-16 02:07:18,135 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2023-02-16 02:07:18,136 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:18,136 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:18,146 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-16 02:07:18,342 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-16 02:07:18,342 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:18,343 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:18,343 INFO L85 PathProgramCache]: Analyzing trace with hash -1145481658, now seen corresponding path program 1 times [2023-02-16 02:07:18,343 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:18,343 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1969905322] [2023-02-16 02:07:18,343 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:18,343 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:18,351 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:18,351 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [186370569] [2023-02-16 02:07:18,351 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:18,351 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:18,352 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:18,353 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-16 02:07:18,355 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-16 02:07:18,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:18,401 INFO L263 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 5 conjunts are in the unsatisfiable core [2023-02-16 02:07:18,403 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:18,449 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-02-16 02:07:18,449 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-16 02:07:18,450 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:18,450 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1969905322] [2023-02-16 02:07:18,450 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:18,450 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [186370569] [2023-02-16 02:07:18,450 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [186370569] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-16 02:07:18,450 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-16 02:07:18,451 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-02-16 02:07:18,451 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1123562746] [2023-02-16 02:07:18,451 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 02:07:18,451 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-16 02:07:18,451 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:18,452 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-16 02:07:18,452 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-02-16 02:07:18,452 INFO L87 Difference]: Start difference. First operand 48 states and 62 transitions. Second operand has 5 states, 5 states have (on average 4.2) internal successors, (21), 4 states have internal predecessors, (21), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-02-16 02:07:18,496 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:18,496 INFO L93 Difference]: Finished difference Result 93 states and 121 transitions. [2023-02-16 02:07:18,496 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-02-16 02:07:18,497 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 4 states have internal predecessors, (21), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 31 [2023-02-16 02:07:18,497 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:18,499 INFO L225 Difference]: With dead ends: 93 [2023-02-16 02:07:18,499 INFO L226 Difference]: Without dead ends: 56 [2023-02-16 02:07:18,500 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 27 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-16 02:07:18,502 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 0 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 109 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:18,502 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 109 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 18 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-16 02:07:18,503 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2023-02-16 02:07:18,519 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2023-02-16 02:07:18,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 41 states have (on average 1.2439024390243902) internal successors, (51), 41 states have internal predecessors, (51), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-02-16 02:07:18,520 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 70 transitions. [2023-02-16 02:07:18,520 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 70 transitions. Word has length 31 [2023-02-16 02:07:18,521 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:18,521 INFO L495 AbstractCegarLoop]: Abstraction has 56 states and 70 transitions. [2023-02-16 02:07:18,521 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 4 states have internal predecessors, (21), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-02-16 02:07:18,521 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 70 transitions. [2023-02-16 02:07:18,522 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2023-02-16 02:07:18,522 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:18,522 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:18,531 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-16 02:07:18,728 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-16 02:07:18,729 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:18,729 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:18,729 INFO L85 PathProgramCache]: Analyzing trace with hash -1102972225, now seen corresponding path program 1 times [2023-02-16 02:07:18,730 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:18,730 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [8810470] [2023-02-16 02:07:18,730 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:18,730 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:18,741 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:18,743 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1755249381] [2023-02-16 02:07:18,743 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:18,743 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:18,743 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:18,744 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-16 02:07:18,747 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-16 02:07:18,788 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:18,789 INFO L263 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-16 02:07:18,793 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:18,847 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-02-16 02:07:18,847 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 02:07:18,909 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-02-16 02:07:18,910 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:18,910 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [8810470] [2023-02-16 02:07:18,911 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:18,911 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1755249381] [2023-02-16 02:07:18,911 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1755249381] provided 1 perfect and 1 imperfect interpolant sequences [2023-02-16 02:07:18,911 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-02-16 02:07:18,911 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [5] total 10 [2023-02-16 02:07:18,911 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [166616357] [2023-02-16 02:07:18,912 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 02:07:18,912 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-02-16 02:07:18,913 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:18,913 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-02-16 02:07:18,913 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2023-02-16 02:07:18,914 INFO L87 Difference]: Start difference. First operand 56 states and 70 transitions. Second operand has 6 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 6 states have internal predecessors, (22), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-02-16 02:07:18,958 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:18,958 INFO L93 Difference]: Finished difference Result 102 states and 131 transitions. [2023-02-16 02:07:18,958 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-16 02:07:18,959 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 6 states have internal predecessors, (22), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 37 [2023-02-16 02:07:18,959 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:18,961 INFO L225 Difference]: With dead ends: 102 [2023-02-16 02:07:18,961 INFO L226 Difference]: Without dead ends: 65 [2023-02-16 02:07:18,961 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2023-02-16 02:07:18,962 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 14 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:18,962 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 129 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-16 02:07:18,964 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2023-02-16 02:07:18,989 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 64. [2023-02-16 02:07:18,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 47 states have (on average 1.2340425531914894) internal successors, (58), 47 states have internal predecessors, (58), 11 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-02-16 02:07:18,990 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 79 transitions. [2023-02-16 02:07:18,990 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 79 transitions. Word has length 37 [2023-02-16 02:07:18,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:18,991 INFO L495 AbstractCegarLoop]: Abstraction has 64 states and 79 transitions. [2023-02-16 02:07:18,991 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 6 states have internal predecessors, (22), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-02-16 02:07:18,991 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 79 transitions. [2023-02-16 02:07:18,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2023-02-16 02:07:18,992 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:18,992 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:18,999 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-16 02:07:19,198 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-16 02:07:19,199 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:19,199 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:19,199 INFO L85 PathProgramCache]: Analyzing trace with hash 30895492, now seen corresponding path program 1 times [2023-02-16 02:07:19,199 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:19,199 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [645701347] [2023-02-16 02:07:19,200 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:19,200 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:19,207 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:19,207 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1737713792] [2023-02-16 02:07:19,208 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:19,208 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:19,208 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:19,209 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-16 02:07:19,212 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-16 02:07:19,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:19,259 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-16 02:07:19,262 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:19,310 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-02-16 02:07:19,311 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 02:07:19,382 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-02-16 02:07:19,383 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:19,383 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [645701347] [2023-02-16 02:07:19,383 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:19,383 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1737713792] [2023-02-16 02:07:19,383 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1737713792] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 02:07:19,383 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 02:07:19,384 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 10 [2023-02-16 02:07:19,384 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [362714450] [2023-02-16 02:07:19,384 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 02:07:19,384 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-02-16 02:07:19,384 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:19,385 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-02-16 02:07:19,385 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2023-02-16 02:07:19,385 INFO L87 Difference]: Start difference. First operand 64 states and 79 transitions. Second operand has 10 states, 10 states have (on average 4.4) internal successors, (44), 10 states have internal predecessors, (44), 7 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2023-02-16 02:07:19,535 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:19,535 INFO L93 Difference]: Finished difference Result 189 states and 243 transitions. [2023-02-16 02:07:19,535 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-02-16 02:07:19,536 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.4) internal successors, (44), 10 states have internal predecessors, (44), 7 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) Word has length 39 [2023-02-16 02:07:19,536 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:19,537 INFO L225 Difference]: With dead ends: 189 [2023-02-16 02:07:19,537 INFO L226 Difference]: Without dead ends: 152 [2023-02-16 02:07:19,539 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 68 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2023-02-16 02:07:19,540 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 52 mSDsluCounter, 170 mSDsCounter, 0 mSdLazyCounter, 73 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 79 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 73 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:19,540 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 212 Invalid, 79 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 73 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-16 02:07:19,541 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2023-02-16 02:07:19,581 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 136. [2023-02-16 02:07:19,585 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 101 states have (on average 1.2475247524752475) internal successors, (126), 103 states have internal predecessors, (126), 23 states have call successors, (23), 12 states have call predecessors, (23), 11 states have return successors, (22), 20 states have call predecessors, (22), 22 states have call successors, (22) [2023-02-16 02:07:19,586 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 171 transitions. [2023-02-16 02:07:19,586 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 171 transitions. Word has length 39 [2023-02-16 02:07:19,587 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:19,587 INFO L495 AbstractCegarLoop]: Abstraction has 136 states and 171 transitions. [2023-02-16 02:07:19,587 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.4) internal successors, (44), 10 states have internal predecessors, (44), 7 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2023-02-16 02:07:19,587 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 171 transitions. [2023-02-16 02:07:19,590 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-02-16 02:07:19,591 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:19,591 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:19,599 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-16 02:07:19,796 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-16 02:07:19,796 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:19,797 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:19,797 INFO L85 PathProgramCache]: Analyzing trace with hash -798356602, now seen corresponding path program 1 times [2023-02-16 02:07:19,797 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:19,797 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [163804327] [2023-02-16 02:07:19,797 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:19,797 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:19,804 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:19,804 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1827327918] [2023-02-16 02:07:19,804 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:19,805 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:19,805 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:19,806 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-16 02:07:19,808 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-16 02:07:19,852 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:19,853 INFO L263 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 3 conjunts are in the unsatisfiable core [2023-02-16 02:07:19,854 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:19,883 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-02-16 02:07:19,884 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-16 02:07:19,884 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:19,884 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [163804327] [2023-02-16 02:07:19,884 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:19,884 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1827327918] [2023-02-16 02:07:19,884 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1827327918] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-16 02:07:19,884 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-16 02:07:19,885 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-02-16 02:07:19,885 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1087385110] [2023-02-16 02:07:19,885 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 02:07:19,885 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-02-16 02:07:19,885 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:19,886 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-02-16 02:07:19,886 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2023-02-16 02:07:19,886 INFO L87 Difference]: Start difference. First operand 136 states and 171 transitions. Second operand has 4 states, 4 states have (on average 5.75) internal successors, (23), 4 states have internal predecessors, (23), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2023-02-16 02:07:19,942 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:19,943 INFO L93 Difference]: Finished difference Result 231 states and 306 transitions. [2023-02-16 02:07:19,943 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-02-16 02:07:19,943 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 5.75) internal successors, (23), 4 states have internal predecessors, (23), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 43 [2023-02-16 02:07:19,944 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:19,946 INFO L225 Difference]: With dead ends: 231 [2023-02-16 02:07:19,946 INFO L226 Difference]: Without dead ends: 176 [2023-02-16 02:07:19,947 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2023-02-16 02:07:19,947 INFO L413 NwaCegarLoop]: 49 mSDtfsCounter, 20 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:19,948 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 85 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-16 02:07:19,948 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 176 states. [2023-02-16 02:07:19,977 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 176 to 158. [2023-02-16 02:07:19,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 158 states, 118 states have (on average 1.2542372881355932) internal successors, (148), 120 states have internal predecessors, (148), 28 states have call successors, (28), 12 states have call predecessors, (28), 11 states have return successors, (27), 25 states have call predecessors, (27), 27 states have call successors, (27) [2023-02-16 02:07:19,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 203 transitions. [2023-02-16 02:07:19,979 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 203 transitions. Word has length 43 [2023-02-16 02:07:19,979 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:19,979 INFO L495 AbstractCegarLoop]: Abstraction has 158 states and 203 transitions. [2023-02-16 02:07:19,979 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 5.75) internal successors, (23), 4 states have internal predecessors, (23), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2023-02-16 02:07:19,980 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 203 transitions. [2023-02-16 02:07:19,980 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-02-16 02:07:19,980 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:19,981 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:19,989 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-16 02:07:20,186 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-16 02:07:20,186 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:20,186 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:20,187 INFO L85 PathProgramCache]: Analyzing trace with hash -1023958197, now seen corresponding path program 1 times [2023-02-16 02:07:20,187 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:20,187 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1356793385] [2023-02-16 02:07:20,187 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:20,187 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:20,194 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:20,194 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [98259233] [2023-02-16 02:07:20,194 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:20,194 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:20,195 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:20,196 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-16 02:07:20,204 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-16 02:07:20,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:20,241 INFO L263 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 9 conjunts are in the unsatisfiable core [2023-02-16 02:07:20,243 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:20,306 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 8 proven. 14 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-02-16 02:07:20,307 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 02:07:20,379 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-02-16 02:07:20,379 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:20,379 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1356793385] [2023-02-16 02:07:20,379 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:20,379 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [98259233] [2023-02-16 02:07:20,380 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [98259233] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 02:07:20,380 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 02:07:20,380 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 7] total 12 [2023-02-16 02:07:20,380 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [924259204] [2023-02-16 02:07:20,380 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 02:07:20,381 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-02-16 02:07:20,381 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:20,381 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-02-16 02:07:20,382 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2023-02-16 02:07:20,382 INFO L87 Difference]: Start difference. First operand 158 states and 203 transitions. Second operand has 12 states, 12 states have (on average 4.25) internal successors, (51), 12 states have internal predecessors, (51), 9 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) [2023-02-16 02:07:20,567 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:20,567 INFO L93 Difference]: Finished difference Result 347 states and 460 transitions. [2023-02-16 02:07:20,568 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-02-16 02:07:20,568 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 4.25) internal successors, (51), 12 states have internal predecessors, (51), 9 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) Word has length 45 [2023-02-16 02:07:20,568 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:20,570 INFO L225 Difference]: With dead ends: 347 [2023-02-16 02:07:20,570 INFO L226 Difference]: Without dead ends: 262 [2023-02-16 02:07:20,571 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=92, Invalid=180, Unknown=0, NotChecked=0, Total=272 [2023-02-16 02:07:20,571 INFO L413 NwaCegarLoop]: 47 mSDtfsCounter, 75 mSDsluCounter, 203 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 75 SdHoareTripleChecker+Valid, 250 SdHoareTripleChecker+Invalid, 108 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:20,571 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [75 Valid, 250 Invalid, 108 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 99 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-16 02:07:20,572 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 262 states. [2023-02-16 02:07:20,622 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 262 to 240. [2023-02-16 02:07:20,623 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 240 states, 180 states have (on average 1.25) internal successors, (225), 182 states have internal predecessors, (225), 44 states have call successors, (44), 16 states have call predecessors, (44), 15 states have return successors, (43), 41 states have call predecessors, (43), 43 states have call successors, (43) [2023-02-16 02:07:20,625 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 240 states to 240 states and 312 transitions. [2023-02-16 02:07:20,625 INFO L78 Accepts]: Start accepts. Automaton has 240 states and 312 transitions. Word has length 45 [2023-02-16 02:07:20,626 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:20,626 INFO L495 AbstractCegarLoop]: Abstraction has 240 states and 312 transitions. [2023-02-16 02:07:20,626 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 4.25) internal successors, (51), 12 states have internal predecessors, (51), 9 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) [2023-02-16 02:07:20,627 INFO L276 IsEmpty]: Start isEmpty. Operand 240 states and 312 transitions. [2023-02-16 02:07:20,630 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2023-02-16 02:07:20,630 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:20,630 INFO L195 NwaCegarLoop]: trace histogram [5, 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, 1, 1] [2023-02-16 02:07:20,638 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-02-16 02:07:20,835 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-16 02:07:20,836 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:20,836 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:20,836 INFO L85 PathProgramCache]: Analyzing trace with hash -1104536814, now seen corresponding path program 1 times [2023-02-16 02:07:20,836 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:20,837 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2032004817] [2023-02-16 02:07:20,837 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:20,837 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:20,845 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:20,845 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1754756631] [2023-02-16 02:07:20,845 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:20,845 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:20,846 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:20,847 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-16 02:07:20,850 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-16 02:07:20,889 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:20,890 INFO L263 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 11 conjunts are in the unsatisfiable core [2023-02-16 02:07:20,891 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:20,974 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 8 proven. 30 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-02-16 02:07:20,974 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 02:07:21,079 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 8 proven. 6 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-02-16 02:07:21,079 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:21,080 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2032004817] [2023-02-16 02:07:21,080 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:21,080 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1754756631] [2023-02-16 02:07:21,080 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1754756631] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 02:07:21,080 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 02:07:21,080 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 14 [2023-02-16 02:07:21,081 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1899355717] [2023-02-16 02:07:21,082 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 02:07:21,082 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-02-16 02:07:21,082 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:21,083 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-02-16 02:07:21,083 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2023-02-16 02:07:21,083 INFO L87 Difference]: Start difference. First operand 240 states and 312 transitions. Second operand has 14 states, 14 states have (on average 4.142857142857143) internal successors, (58), 14 states have internal predecessors, (58), 11 states have call successors, (13), 7 states have call predecessors, (13), 6 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) [2023-02-16 02:07:21,329 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:21,329 INFO L93 Difference]: Finished difference Result 342 states and 455 transitions. [2023-02-16 02:07:21,330 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2023-02-16 02:07:21,330 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.142857142857143) internal successors, (58), 14 states have internal predecessors, (58), 11 states have call successors, (13), 7 states have call predecessors, (13), 6 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) Word has length 51 [2023-02-16 02:07:21,330 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:21,332 INFO L225 Difference]: With dead ends: 342 [2023-02-16 02:07:21,332 INFO L226 Difference]: Without dead ends: 337 [2023-02-16 02:07:21,332 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 88 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=130, Invalid=250, Unknown=0, NotChecked=0, Total=380 [2023-02-16 02:07:21,333 INFO L413 NwaCegarLoop]: 53 mSDtfsCounter, 133 mSDsluCounter, 183 mSDsCounter, 0 mSdLazyCounter, 138 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 133 SdHoareTripleChecker+Valid, 236 SdHoareTripleChecker+Invalid, 184 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 138 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:21,333 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [133 Valid, 236 Invalid, 184 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 138 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-16 02:07:21,334 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 337 states. [2023-02-16 02:07:21,393 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 337 to 323. [2023-02-16 02:07:21,394 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 323 states, 241 states have (on average 1.2323651452282158) internal successors, (297), 248 states have internal predecessors, (297), 62 states have call successors, (62), 20 states have call predecessors, (62), 19 states have return successors, (61), 54 states have call predecessors, (61), 61 states have call successors, (61) [2023-02-16 02:07:21,395 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 323 states to 323 states and 420 transitions. [2023-02-16 02:07:21,396 INFO L78 Accepts]: Start accepts. Automaton has 323 states and 420 transitions. Word has length 51 [2023-02-16 02:07:21,396 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:21,396 INFO L495 AbstractCegarLoop]: Abstraction has 323 states and 420 transitions. [2023-02-16 02:07:21,396 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.142857142857143) internal successors, (58), 14 states have internal predecessors, (58), 11 states have call successors, (13), 7 states have call predecessors, (13), 6 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) [2023-02-16 02:07:21,396 INFO L276 IsEmpty]: Start isEmpty. Operand 323 states and 420 transitions. [2023-02-16 02:07:21,398 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2023-02-16 02:07:21,398 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:21,398 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 5, 4, 4, 4, 3, 3, 3, 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-16 02:07:21,406 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-16 02:07:21,603 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-16 02:07:21,603 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:21,603 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:21,603 INFO L85 PathProgramCache]: Analyzing trace with hash 540498080, now seen corresponding path program 1 times [2023-02-16 02:07:21,603 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:21,604 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [556875359] [2023-02-16 02:07:21,604 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:21,604 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:21,612 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:21,612 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [373185236] [2023-02-16 02:07:21,612 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:21,612 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:21,612 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:21,615 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-16 02:07:21,617 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-16 02:07:21,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:21,672 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 4 conjunts are in the unsatisfiable core [2023-02-16 02:07:21,675 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:21,726 INFO L134 CoverageAnalysis]: Checked inductivity of 180 backedges. 64 proven. 12 refuted. 0 times theorem prover too weak. 104 trivial. 0 not checked. [2023-02-16 02:07:21,726 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 02:07:21,793 INFO L134 CoverageAnalysis]: Checked inductivity of 180 backedges. 38 proven. 12 refuted. 0 times theorem prover too weak. 130 trivial. 0 not checked. [2023-02-16 02:07:21,793 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:21,793 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [556875359] [2023-02-16 02:07:21,794 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:21,794 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [373185236] [2023-02-16 02:07:21,794 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [373185236] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 02:07:21,794 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 02:07:21,794 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2023-02-16 02:07:21,794 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [22330944] [2023-02-16 02:07:21,794 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 02:07:21,794 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-02-16 02:07:21,794 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:21,795 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-02-16 02:07:21,795 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-02-16 02:07:21,795 INFO L87 Difference]: Start difference. First operand 323 states and 420 transitions. Second operand has 4 states, 4 states have (on average 9.0) internal successors, (36), 4 states have internal predecessors, (36), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2023-02-16 02:07:21,909 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:21,909 INFO L93 Difference]: Finished difference Result 579 states and 783 transitions. [2023-02-16 02:07:21,910 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-02-16 02:07:21,910 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 9.0) internal successors, (36), 4 states have internal predecessors, (36), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 87 [2023-02-16 02:07:21,910 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:21,914 INFO L225 Difference]: With dead ends: 579 [2023-02-16 02:07:21,914 INFO L226 Difference]: Without dead ends: 387 [2023-02-16 02:07:21,915 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 168 SyntacticMatches, 2 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-02-16 02:07:21,915 INFO L413 NwaCegarLoop]: 62 mSDtfsCounter, 18 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:21,916 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 125 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-16 02:07:21,916 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 387 states. [2023-02-16 02:07:21,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 387 to 384. [2023-02-16 02:07:21,988 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 384 states, 290 states have (on average 1.2413793103448276) internal successors, (360), 296 states have internal predecessors, (360), 74 states have call successors, (74), 20 states have call predecessors, (74), 19 states have return successors, (73), 67 states have call predecessors, (73), 73 states have call successors, (73) [2023-02-16 02:07:21,991 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 384 states to 384 states and 507 transitions. [2023-02-16 02:07:21,991 INFO L78 Accepts]: Start accepts. Automaton has 384 states and 507 transitions. Word has length 87 [2023-02-16 02:07:21,992 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:21,992 INFO L495 AbstractCegarLoop]: Abstraction has 384 states and 507 transitions. [2023-02-16 02:07:21,993 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 9.0) internal successors, (36), 4 states have internal predecessors, (36), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2023-02-16 02:07:21,993 INFO L276 IsEmpty]: Start isEmpty. Operand 384 states and 507 transitions. [2023-02-16 02:07:21,994 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2023-02-16 02:07:21,994 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:21,994 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:22,002 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-16 02:07:22,200 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-16 02:07:22,200 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:22,201 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:22,201 INFO L85 PathProgramCache]: Analyzing trace with hash -134976430, now seen corresponding path program 2 times [2023-02-16 02:07:22,201 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:22,201 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1391212866] [2023-02-16 02:07:22,201 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:22,201 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:22,219 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:22,220 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1328783275] [2023-02-16 02:07:22,220 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-16 02:07:22,221 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:22,221 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:22,222 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-16 02:07:22,224 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-16 02:07:22,296 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-16 02:07:22,296 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 02:07:22,297 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 17 conjunts are in the unsatisfiable core [2023-02-16 02:07:22,299 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:22,441 INFO L134 CoverageAnalysis]: Checked inductivity of 176 backedges. 58 proven. 110 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-02-16 02:07:22,442 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 02:07:22,625 INFO L134 CoverageAnalysis]: Checked inductivity of 176 backedges. 32 proven. 26 refuted. 0 times theorem prover too weak. 118 trivial. 0 not checked. [2023-02-16 02:07:22,625 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:22,625 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1391212866] [2023-02-16 02:07:22,625 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:22,625 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1328783275] [2023-02-16 02:07:22,625 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1328783275] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 02:07:22,625 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 02:07:22,626 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 20 [2023-02-16 02:07:22,626 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1073615791] [2023-02-16 02:07:22,626 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 02:07:22,626 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2023-02-16 02:07:22,626 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:22,627 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2023-02-16 02:07:22,627 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=158, Invalid=222, Unknown=0, NotChecked=0, Total=380 [2023-02-16 02:07:22,627 INFO L87 Difference]: Start difference. First operand 384 states and 507 transitions. Second operand has 20 states, 20 states have (on average 4.65) internal successors, (93), 20 states have internal predecessors, (93), 17 states have call successors, (21), 10 states have call predecessors, (21), 10 states have return successors, (20), 17 states have call predecessors, (20), 17 states have call successors, (20) [2023-02-16 02:07:23,174 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:23,175 INFO L93 Difference]: Finished difference Result 1131 states and 1582 transitions. [2023-02-16 02:07:23,175 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2023-02-16 02:07:23,175 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 4.65) internal successors, (93), 20 states have internal predecessors, (93), 17 states have call successors, (21), 10 states have call predecessors, (21), 10 states have return successors, (20), 17 states have call predecessors, (20), 17 states have call successors, (20) Word has length 87 [2023-02-16 02:07:23,176 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:23,179 INFO L225 Difference]: With dead ends: 1131 [2023-02-16 02:07:23,179 INFO L226 Difference]: Without dead ends: 966 [2023-02-16 02:07:23,180 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 186 GetRequests, 154 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 134 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=403, Invalid=719, Unknown=0, NotChecked=0, Total=1122 [2023-02-16 02:07:23,181 INFO L413 NwaCegarLoop]: 71 mSDtfsCounter, 263 mSDsluCounter, 365 mSDsCounter, 0 mSdLazyCounter, 233 mSolverCounterSat, 104 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 263 SdHoareTripleChecker+Valid, 436 SdHoareTripleChecker+Invalid, 337 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 104 IncrementalHoareTripleChecker+Valid, 233 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:23,181 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [263 Valid, 436 Invalid, 337 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [104 Valid, 233 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-02-16 02:07:23,182 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 966 states. [2023-02-16 02:07:23,340 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 966 to 911. [2023-02-16 02:07:23,342 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 911 states, 691 states have (on average 1.2416787264833575) internal successors, (858), 702 states have internal predecessors, (858), 188 states have call successors, (188), 32 states have call predecessors, (188), 31 states have return successors, (187), 176 states have call predecessors, (187), 187 states have call successors, (187) [2023-02-16 02:07:23,346 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 911 states to 911 states and 1233 transitions. [2023-02-16 02:07:23,346 INFO L78 Accepts]: Start accepts. Automaton has 911 states and 1233 transitions. Word has length 87 [2023-02-16 02:07:23,347 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:23,347 INFO L495 AbstractCegarLoop]: Abstraction has 911 states and 1233 transitions. [2023-02-16 02:07:23,347 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 4.65) internal successors, (93), 20 states have internal predecessors, (93), 17 states have call successors, (21), 10 states have call predecessors, (21), 10 states have return successors, (20), 17 states have call predecessors, (20), 17 states have call successors, (20) [2023-02-16 02:07:23,348 INFO L276 IsEmpty]: Start isEmpty. Operand 911 states and 1233 transitions. [2023-02-16 02:07:23,353 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2023-02-16 02:07:23,353 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:23,354 INFO L195 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:23,363 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-16 02:07:23,559 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-16 02:07:23,560 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:23,560 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:23,560 INFO L85 PathProgramCache]: Analyzing trace with hash 2132027339, now seen corresponding path program 1 times [2023-02-16 02:07:23,560 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:23,561 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [472755800] [2023-02-16 02:07:23,561 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:23,561 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:23,569 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:23,569 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [947628074] [2023-02-16 02:07:23,569 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:23,569 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:23,569 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:23,570 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-16 02:07:23,573 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-16 02:07:23,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:23,628 INFO L263 TraceCheckSpWp]: Trace formula consists of 225 conjuncts, 21 conjunts are in the unsatisfiable core [2023-02-16 02:07:23,630 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:23,776 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 22 proven. 190 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-02-16 02:07:23,776 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 02:07:24,002 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 22 proven. 46 refuted. 0 times theorem prover too weak. 148 trivial. 0 not checked. [2023-02-16 02:07:24,002 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:24,002 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [472755800] [2023-02-16 02:07:24,002 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:24,002 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [947628074] [2023-02-16 02:07:24,002 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [947628074] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 02:07:24,002 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 02:07:24,002 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 24 [2023-02-16 02:07:24,003 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1982899546] [2023-02-16 02:07:24,003 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 02:07:24,003 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2023-02-16 02:07:24,003 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:24,004 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2023-02-16 02:07:24,004 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=236, Invalid=316, Unknown=0, NotChecked=0, Total=552 [2023-02-16 02:07:24,004 INFO L87 Difference]: Start difference. First operand 911 states and 1233 transitions. Second operand has 24 states, 24 states have (on average 4.375) internal successors, (105), 24 states have internal predecessors, (105), 21 states have call successors, (23), 12 states have call predecessors, (23), 11 states have return successors, (22), 20 states have call predecessors, (22), 20 states have call successors, (22) [2023-02-16 02:07:24,734 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:24,734 INFO L93 Difference]: Finished difference Result 1475 states and 1988 transitions. [2023-02-16 02:07:24,735 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2023-02-16 02:07:24,735 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 4.375) internal successors, (105), 24 states have internal predecessors, (105), 21 states have call successors, (23), 12 states have call predecessors, (23), 11 states have return successors, (22), 20 states have call predecessors, (22), 20 states have call successors, (22) Word has length 93 [2023-02-16 02:07:24,736 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:24,739 INFO L225 Difference]: With dead ends: 1475 [2023-02-16 02:07:24,739 INFO L226 Difference]: Without dead ends: 873 [2023-02-16 02:07:24,741 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 201 GetRequests, 162 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 200 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=584, Invalid=1056, Unknown=0, NotChecked=0, Total=1640 [2023-02-16 02:07:24,741 INFO L413 NwaCegarLoop]: 83 mSDtfsCounter, 434 mSDsluCounter, 414 mSDsCounter, 0 mSdLazyCounter, 335 mSolverCounterSat, 213 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 434 SdHoareTripleChecker+Valid, 497 SdHoareTripleChecker+Invalid, 548 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 213 IncrementalHoareTripleChecker+Valid, 335 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:24,742 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [434 Valid, 497 Invalid, 548 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [213 Valid, 335 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-02-16 02:07:24,743 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 873 states. [2023-02-16 02:07:24,850 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 873 to 818. [2023-02-16 02:07:24,852 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 818 states, 614 states have (on average 1.201954397394137) internal successors, (738), 618 states have internal predecessors, (738), 164 states have call successors, (164), 40 states have call predecessors, (164), 39 states have return successors, (163), 159 states have call predecessors, (163), 163 states have call successors, (163) [2023-02-16 02:07:24,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 818 states to 818 states and 1065 transitions. [2023-02-16 02:07:24,855 INFO L78 Accepts]: Start accepts. Automaton has 818 states and 1065 transitions. Word has length 93 [2023-02-16 02:07:24,855 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:24,855 INFO L495 AbstractCegarLoop]: Abstraction has 818 states and 1065 transitions. [2023-02-16 02:07:24,856 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 4.375) internal successors, (105), 24 states have internal predecessors, (105), 21 states have call successors, (23), 12 states have call predecessors, (23), 11 states have return successors, (22), 20 states have call predecessors, (22), 20 states have call successors, (22) [2023-02-16 02:07:24,856 INFO L276 IsEmpty]: Start isEmpty. Operand 818 states and 1065 transitions. [2023-02-16 02:07:24,857 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2023-02-16 02:07:24,857 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:24,857 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:24,863 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-16 02:07:25,063 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-16 02:07:25,063 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:25,064 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:25,064 INFO L85 PathProgramCache]: Analyzing trace with hash 519126930, now seen corresponding path program 1 times [2023-02-16 02:07:25,064 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:25,064 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1187441656] [2023-02-16 02:07:25,064 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:25,064 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:25,072 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:25,072 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1855954808] [2023-02-16 02:07:25,072 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:25,072 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:25,072 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:25,073 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-16 02:07:25,076 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-16 02:07:25,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:25,131 INFO L263 TraceCheckSpWp]: Trace formula consists of 235 conjuncts, 23 conjunts are in the unsatisfiable core [2023-02-16 02:07:25,133 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:25,302 INFO L134 CoverageAnalysis]: Checked inductivity of 260 backedges. 20 proven. 236 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-02-16 02:07:25,302 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 02:07:25,551 INFO L134 CoverageAnalysis]: Checked inductivity of 260 backedges. 20 proven. 56 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2023-02-16 02:07:25,551 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:25,551 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1187441656] [2023-02-16 02:07:25,552 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:25,552 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1855954808] [2023-02-16 02:07:25,552 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1855954808] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 02:07:25,552 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 02:07:25,552 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14] total 26 [2023-02-16 02:07:25,552 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [105298966] [2023-02-16 02:07:25,552 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 02:07:25,553 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-02-16 02:07:25,553 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:25,554 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-02-16 02:07:25,554 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=281, Invalid=369, Unknown=0, NotChecked=0, Total=650 [2023-02-16 02:07:25,554 INFO L87 Difference]: Start difference. First operand 818 states and 1065 transitions. Second operand has 26 states, 26 states have (on average 4.3076923076923075) internal successors, (112), 26 states have internal predecessors, (112), 23 states have call successors, (25), 13 states have call predecessors, (25), 12 states have return successors, (24), 22 states have call predecessors, (24), 22 states have call successors, (24) [2023-02-16 02:07:26,216 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:26,216 INFO L93 Difference]: Finished difference Result 941 states and 1237 transitions. [2023-02-16 02:07:26,216 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2023-02-16 02:07:26,217 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 4.3076923076923075) internal successors, (112), 26 states have internal predecessors, (112), 23 states have call successors, (25), 13 states have call predecessors, (25), 12 states have return successors, (24), 22 states have call predecessors, (24), 22 states have call successors, (24) Word has length 99 [2023-02-16 02:07:26,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:26,220 INFO L225 Difference]: With dead ends: 941 [2023-02-16 02:07:26,221 INFO L226 Difference]: Without dead ends: 936 [2023-02-16 02:07:26,221 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 214 GetRequests, 172 SyntacticMatches, 0 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 229 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=670, Invalid=1222, Unknown=0, NotChecked=0, Total=1892 [2023-02-16 02:07:26,222 INFO L413 NwaCegarLoop]: 89 mSDtfsCounter, 360 mSDsluCounter, 334 mSDsCounter, 0 mSdLazyCounter, 276 mSolverCounterSat, 174 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 360 SdHoareTripleChecker+Valid, 423 SdHoareTripleChecker+Invalid, 450 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 174 IncrementalHoareTripleChecker+Valid, 276 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:26,222 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [360 Valid, 423 Invalid, 450 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [174 Valid, 276 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-02-16 02:07:26,223 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 936 states. [2023-02-16 02:07:26,323 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 936 to 920. [2023-02-16 02:07:26,325 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 920 states, 692 states have (on average 1.1820809248554913) internal successors, (818), 698 states have internal predecessors, (818), 184 states have call successors, (184), 44 states have call predecessors, (184), 43 states have return successors, (183), 177 states have call predecessors, (183), 183 states have call successors, (183) [2023-02-16 02:07:26,328 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 920 states to 920 states and 1185 transitions. [2023-02-16 02:07:26,328 INFO L78 Accepts]: Start accepts. Automaton has 920 states and 1185 transitions. Word has length 99 [2023-02-16 02:07:26,328 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:26,329 INFO L495 AbstractCegarLoop]: Abstraction has 920 states and 1185 transitions. [2023-02-16 02:07:26,329 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 4.3076923076923075) internal successors, (112), 26 states have internal predecessors, (112), 23 states have call successors, (25), 13 states have call predecessors, (25), 12 states have return successors, (24), 22 states have call predecessors, (24), 22 states have call successors, (24) [2023-02-16 02:07:26,329 INFO L276 IsEmpty]: Start isEmpty. Operand 920 states and 1185 transitions. [2023-02-16 02:07:26,333 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 178 [2023-02-16 02:07:26,333 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:26,333 INFO L195 NwaCegarLoop]: trace histogram [20, 19, 19, 9, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:26,341 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2023-02-16 02:07:26,538 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-16 02:07:26,539 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:26,539 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:26,539 INFO L85 PathProgramCache]: Analyzing trace with hash 1985812011, now seen corresponding path program 3 times [2023-02-16 02:07:26,539 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:26,539 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [657839539] [2023-02-16 02:07:26,540 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:26,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:26,559 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:26,563 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [894111039] [2023-02-16 02:07:26,563 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-16 02:07:26,563 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:26,563 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:26,564 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-16 02:07:26,567 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-16 02:07:26,629 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-02-16 02:07:26,629 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 02:07:26,630 INFO L263 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 4 conjunts are in the unsatisfiable core [2023-02-16 02:07:26,633 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:26,649 INFO L134 CoverageAnalysis]: Checked inductivity of 984 backedges. 255 proven. 0 refuted. 0 times theorem prover too weak. 729 trivial. 0 not checked. [2023-02-16 02:07:26,649 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-16 02:07:26,650 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:26,650 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [657839539] [2023-02-16 02:07:26,650 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:26,650 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [894111039] [2023-02-16 02:07:26,650 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [894111039] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-16 02:07:26,650 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-16 02:07:26,650 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-02-16 02:07:26,651 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1101554114] [2023-02-16 02:07:26,651 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 02:07:26,651 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-16 02:07:26,651 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:26,652 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-16 02:07:26,652 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-02-16 02:07:26,652 INFO L87 Difference]: Start difference. First operand 920 states and 1185 transitions. Second operand has 5 states, 5 states have (on average 7.6) internal successors, (38), 5 states have internal predecessors, (38), 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-16 02:07:26,782 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:26,782 INFO L93 Difference]: Finished difference Result 1266 states and 1656 transitions. [2023-02-16 02:07:26,783 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-16 02:07:26,783 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 7.6) internal successors, (38), 5 states have internal predecessors, (38), 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 177 [2023-02-16 02:07:26,783 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:26,787 INFO L225 Difference]: With dead ends: 1266 [2023-02-16 02:07:26,787 INFO L226 Difference]: Without dead ends: 1013 [2023-02-16 02:07:26,788 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 173 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-16 02:07:26,788 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 17 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:26,789 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 149 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-16 02:07:26,791 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1013 states. [2023-02-16 02:07:26,915 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1013 to 960. [2023-02-16 02:07:26,917 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 960 states, 726 states have (on average 1.1707988980716253) internal successors, (850), 732 states have internal predecessors, (850), 188 states have call successors, (188), 46 states have call predecessors, (188), 45 states have return successors, (187), 181 states have call predecessors, (187), 187 states have call successors, (187) [2023-02-16 02:07:26,921 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 960 states to 960 states and 1225 transitions. [2023-02-16 02:07:26,922 INFO L78 Accepts]: Start accepts. Automaton has 960 states and 1225 transitions. Word has length 177 [2023-02-16 02:07:26,922 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:26,922 INFO L495 AbstractCegarLoop]: Abstraction has 960 states and 1225 transitions. [2023-02-16 02:07:26,922 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 7.6) internal successors, (38), 5 states have internal predecessors, (38), 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-16 02:07:26,922 INFO L276 IsEmpty]: Start isEmpty. Operand 960 states and 1225 transitions. [2023-02-16 02:07:26,926 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2023-02-16 02:07:26,926 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:26,926 INFO L195 NwaCegarLoop]: trace histogram [21, 20, 20, 11, 10, 10, 10, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:26,939 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-16 02:07:27,132 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-16 02:07:27,132 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:27,132 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:27,133 INFO L85 PathProgramCache]: Analyzing trace with hash 1801897766, now seen corresponding path program 4 times [2023-02-16 02:07:27,133 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:27,133 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1092652357] [2023-02-16 02:07:27,133 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:27,133 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:27,141 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:27,142 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2135457710] [2023-02-16 02:07:27,142 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-02-16 02:07:27,142 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:27,142 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:27,143 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-16 02:07:27,146 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-16 02:07:27,221 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-02-16 02:07:27,221 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 02:07:27,222 INFO L263 TraceCheckSpWp]: Trace formula consists of 355 conjuncts, 2 conjunts are in the unsatisfiable core [2023-02-16 02:07:27,225 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:27,244 INFO L134 CoverageAnalysis]: Checked inductivity of 1104 backedges. 612 proven. 0 refuted. 0 times theorem prover too weak. 492 trivial. 0 not checked. [2023-02-16 02:07:27,244 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-16 02:07:27,244 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:27,245 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1092652357] [2023-02-16 02:07:27,245 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:27,245 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2135457710] [2023-02-16 02:07:27,245 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2135457710] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-16 02:07:27,245 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-16 02:07:27,245 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-02-16 02:07:27,246 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1951186670] [2023-02-16 02:07:27,246 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 02:07:27,246 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-02-16 02:07:27,246 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:27,247 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-02-16 02:07:27,247 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-02-16 02:07:27,247 INFO L87 Difference]: Start difference. First operand 960 states and 1225 transitions. Second operand has 3 states, 3 states have (on average 16.0) internal successors, (48), 3 states have internal predecessors, (48), 3 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-02-16 02:07:27,398 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:27,399 INFO L93 Difference]: Finished difference Result 1545 states and 2001 transitions. [2023-02-16 02:07:27,399 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-02-16 02:07:27,399 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 16.0) internal successors, (48), 3 states have internal predecessors, (48), 3 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 183 [2023-02-16 02:07:27,399 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:27,403 INFO L225 Difference]: With dead ends: 1545 [2023-02-16 02:07:27,403 INFO L226 Difference]: Without dead ends: 1021 [2023-02-16 02:07:27,405 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 182 GetRequests, 181 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-02-16 02:07:27,405 INFO L413 NwaCegarLoop]: 48 mSDtfsCounter, 3 mSDsluCounter, 27 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:27,405 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 75 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-16 02:07:27,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1021 states. [2023-02-16 02:07:27,531 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1021 to 952. [2023-02-16 02:07:27,532 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 952 states, 721 states have (on average 1.1650485436893203) internal successors, (840), 729 states have internal predecessors, (840), 185 states have call successors, (185), 46 states have call predecessors, (185), 45 states have return successors, (184), 176 states have call predecessors, (184), 184 states have call successors, (184) [2023-02-16 02:07:27,536 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 952 states to 952 states and 1209 transitions. [2023-02-16 02:07:27,536 INFO L78 Accepts]: Start accepts. Automaton has 952 states and 1209 transitions. Word has length 183 [2023-02-16 02:07:27,536 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:27,536 INFO L495 AbstractCegarLoop]: Abstraction has 952 states and 1209 transitions. [2023-02-16 02:07:27,537 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 16.0) internal successors, (48), 3 states have internal predecessors, (48), 3 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-02-16 02:07:27,537 INFO L276 IsEmpty]: Start isEmpty. Operand 952 states and 1209 transitions. [2023-02-16 02:07:27,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2023-02-16 02:07:27,541 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:27,541 INFO L195 NwaCegarLoop]: trace histogram [21, 20, 20, 9, 8, 8, 8, 8, 7, 7, 7, 6, 5, 5, 5, 5, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:27,546 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-16 02:07:27,746 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-16 02:07:27,746 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:27,747 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:27,747 INFO L85 PathProgramCache]: Analyzing trace with hash -670817854, now seen corresponding path program 5 times [2023-02-16 02:07:27,747 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:27,747 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [517164773] [2023-02-16 02:07:27,747 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:27,747 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:27,757 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:27,757 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [834880778] [2023-02-16 02:07:27,757 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2023-02-16 02:07:27,758 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:27,758 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:27,759 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-16 02:07:27,761 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-16 02:07:27,916 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 14 check-sat command(s) [2023-02-16 02:07:27,917 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 02:07:27,918 INFO L263 TraceCheckSpWp]: Trace formula consists of 349 conjuncts, 3 conjunts are in the unsatisfiable core [2023-02-16 02:07:27,920 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:27,951 INFO L134 CoverageAnalysis]: Checked inductivity of 1080 backedges. 120 proven. 0 refuted. 0 times theorem prover too weak. 960 trivial. 0 not checked. [2023-02-16 02:07:27,951 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-16 02:07:27,951 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:27,952 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [517164773] [2023-02-16 02:07:27,952 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:27,952 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [834880778] [2023-02-16 02:07:27,952 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [834880778] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-16 02:07:27,952 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-16 02:07:27,952 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-02-16 02:07:27,952 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [579108529] [2023-02-16 02:07:27,953 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 02:07:27,953 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-02-16 02:07:27,953 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:27,954 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-02-16 02:07:27,954 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2023-02-16 02:07:27,954 INFO L87 Difference]: Start difference. First operand 952 states and 1209 transitions. Second operand has 4 states, 4 states have (on average 9.0) internal successors, (36), 4 states have internal predecessors, (36), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2023-02-16 02:07:28,090 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:28,091 INFO L93 Difference]: Finished difference Result 1005 states and 1267 transitions. [2023-02-16 02:07:28,091 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-02-16 02:07:28,091 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 9.0) internal successors, (36), 4 states have internal predecessors, (36), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 183 [2023-02-16 02:07:28,092 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:28,095 INFO L225 Difference]: With dead ends: 1005 [2023-02-16 02:07:28,095 INFO L226 Difference]: Without dead ends: 920 [2023-02-16 02:07:28,096 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 182 GetRequests, 180 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2023-02-16 02:07:28,096 INFO L413 NwaCegarLoop]: 51 mSDtfsCounter, 9 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:28,096 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 114 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-16 02:07:28,097 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 920 states. [2023-02-16 02:07:28,214 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 920 to 899. [2023-02-16 02:07:28,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 899 states, 681 states have (on average 1.15712187958884) internal successors, (788), 688 states have internal predecessors, (788), 172 states have call successors, (172), 46 states have call predecessors, (172), 45 states have return successors, (171), 164 states have call predecessors, (171), 171 states have call successors, (171) [2023-02-16 02:07:28,219 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 899 states to 899 states and 1131 transitions. [2023-02-16 02:07:28,219 INFO L78 Accepts]: Start accepts. Automaton has 899 states and 1131 transitions. Word has length 183 [2023-02-16 02:07:28,220 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:28,220 INFO L495 AbstractCegarLoop]: Abstraction has 899 states and 1131 transitions. [2023-02-16 02:07:28,220 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 9.0) internal successors, (36), 4 states have internal predecessors, (36), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2023-02-16 02:07:28,220 INFO L276 IsEmpty]: Start isEmpty. Operand 899 states and 1131 transitions. [2023-02-16 02:07:28,223 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2023-02-16 02:07:28,223 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:28,223 INFO L195 NwaCegarLoop]: trace histogram [21, 20, 20, 11, 10, 10, 10, 7, 7, 6, 6, 6, 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-16 02:07:28,235 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-16 02:07:28,428 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-16 02:07:28,429 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:28,429 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:28,429 INFO L85 PathProgramCache]: Analyzing trace with hash -1332064508, now seen corresponding path program 6 times [2023-02-16 02:07:28,429 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:28,430 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1792634506] [2023-02-16 02:07:28,430 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:28,430 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:28,444 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:28,444 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1507960963] [2023-02-16 02:07:28,444 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2023-02-16 02:07:28,444 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:28,445 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:28,446 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-16 02:07:28,446 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-16 02:07:30,606 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 12 check-sat command(s) [2023-02-16 02:07:30,607 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 02:07:30,617 INFO L263 TraceCheckSpWp]: Trace formula consists of 419 conjuncts, 22 conjunts are in the unsatisfiable core [2023-02-16 02:07:30,620 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:31,052 INFO L134 CoverageAnalysis]: Checked inductivity of 1108 backedges. 92 proven. 240 refuted. 0 times theorem prover too weak. 776 trivial. 0 not checked. [2023-02-16 02:07:31,052 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 02:07:31,489 INFO L134 CoverageAnalysis]: Checked inductivity of 1108 backedges. 84 proven. 260 refuted. 0 times theorem prover too weak. 764 trivial. 0 not checked. [2023-02-16 02:07:31,489 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:31,489 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1792634506] [2023-02-16 02:07:31,490 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:31,490 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1507960963] [2023-02-16 02:07:31,490 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1507960963] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 02:07:31,490 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 02:07:31,490 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12] total 21 [2023-02-16 02:07:31,490 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2083036824] [2023-02-16 02:07:31,490 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 02:07:31,491 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-02-16 02:07:31,491 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:31,492 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-02-16 02:07:31,492 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=339, Unknown=0, NotChecked=0, Total=420 [2023-02-16 02:07:31,492 INFO L87 Difference]: Start difference. First operand 899 states and 1131 transitions. Second operand has 21 states, 21 states have (on average 6.285714285714286) internal successors, (132), 21 states have internal predecessors, (132), 21 states have call successors, (40), 2 states have call predecessors, (40), 1 states have return successors, (39), 20 states have call predecessors, (39), 20 states have call successors, (39) [2023-02-16 02:07:35,429 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:35,430 INFO L93 Difference]: Finished difference Result 3969 states and 5435 transitions. [2023-02-16 02:07:35,430 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2023-02-16 02:07:35,430 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 6.285714285714286) internal successors, (132), 21 states have internal predecessors, (132), 21 states have call successors, (40), 2 states have call predecessors, (40), 1 states have return successors, (39), 20 states have call predecessors, (39), 20 states have call successors, (39) Word has length 183 [2023-02-16 02:07:35,431 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:35,447 INFO L225 Difference]: With dead ends: 3969 [2023-02-16 02:07:35,447 INFO L226 Difference]: Without dead ends: 3746 [2023-02-16 02:07:35,450 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 414 GetRequests, 345 SyntacticMatches, 0 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1261 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=976, Invalid=3994, Unknown=0, NotChecked=0, Total=4970 [2023-02-16 02:07:35,450 INFO L413 NwaCegarLoop]: 342 mSDtfsCounter, 320 mSDsluCounter, 1500 mSDsCounter, 0 mSdLazyCounter, 2083 mSolverCounterSat, 276 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 324 SdHoareTripleChecker+Valid, 1842 SdHoareTripleChecker+Invalid, 2359 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 276 IncrementalHoareTripleChecker+Valid, 2083 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:35,451 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [324 Valid, 1842 Invalid, 2359 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [276 Valid, 2083 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2023-02-16 02:07:35,454 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3746 states. [2023-02-16 02:07:35,957 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3746 to 2130. [2023-02-16 02:07:35,960 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2130 states, 1611 states have (on average 1.207324643078833) internal successors, (1945), 1637 states have internal predecessors, (1945), 473 states have call successors, (473), 46 states have call predecessors, (473), 45 states have return successors, (472), 446 states have call predecessors, (472), 472 states have call successors, (472) [2023-02-16 02:07:35,971 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2130 states to 2130 states and 2890 transitions. [2023-02-16 02:07:35,971 INFO L78 Accepts]: Start accepts. Automaton has 2130 states and 2890 transitions. Word has length 183 [2023-02-16 02:07:35,972 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:35,972 INFO L495 AbstractCegarLoop]: Abstraction has 2130 states and 2890 transitions. [2023-02-16 02:07:35,972 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 6.285714285714286) internal successors, (132), 21 states have internal predecessors, (132), 21 states have call successors, (40), 2 states have call predecessors, (40), 1 states have return successors, (39), 20 states have call predecessors, (39), 20 states have call successors, (39) [2023-02-16 02:07:35,972 INFO L276 IsEmpty]: Start isEmpty. Operand 2130 states and 2890 transitions. [2023-02-16 02:07:35,980 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2023-02-16 02:07:35,980 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:35,980 INFO L195 NwaCegarLoop]: trace histogram [21, 20, 20, 10, 9, 9, 9, 8, 7, 7, 7, 6, 5, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 02:07:35,988 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-16 02:07:36,180 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-16 02:07:36,181 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:36,181 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:36,181 INFO L85 PathProgramCache]: Analyzing trace with hash -1762868398, now seen corresponding path program 7 times [2023-02-16 02:07:36,181 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:36,181 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2079042720] [2023-02-16 02:07:36,181 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:36,181 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:36,189 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:36,190 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [526366189] [2023-02-16 02:07:36,190 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-02-16 02:07:36,190 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:36,190 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:36,191 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-16 02:07:36,196 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-16 02:07:36,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 02:07:36,275 INFO L263 TraceCheckSpWp]: Trace formula consists of 419 conjuncts, 13 conjunts are in the unsatisfiable core [2023-02-16 02:07:36,278 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:36,405 INFO L134 CoverageAnalysis]: Checked inductivity of 1096 backedges. 516 proven. 84 refuted. 0 times theorem prover too weak. 496 trivial. 0 not checked. [2023-02-16 02:07:36,406 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 02:07:36,574 INFO L134 CoverageAnalysis]: Checked inductivity of 1096 backedges. 226 proven. 84 refuted. 0 times theorem prover too weak. 786 trivial. 0 not checked. [2023-02-16 02:07:36,574 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:36,574 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2079042720] [2023-02-16 02:07:36,574 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:36,574 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [526366189] [2023-02-16 02:07:36,574 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [526366189] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 02:07:36,574 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 02:07:36,574 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2023-02-16 02:07:36,575 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [985051836] [2023-02-16 02:07:36,575 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 02:07:36,575 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-02-16 02:07:36,575 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:36,576 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-02-16 02:07:36,576 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2023-02-16 02:07:36,577 INFO L87 Difference]: Start difference. First operand 2130 states and 2890 transitions. Second operand has 14 states, 14 states have (on average 7.714285714285714) internal successors, (108), 14 states have internal predecessors, (108), 14 states have call successors, (36), 2 states have call predecessors, (36), 2 states have return successors, (35), 14 states have call predecessors, (35), 14 states have call successors, (35) [2023-02-16 02:07:38,118 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:38,118 INFO L93 Difference]: Finished difference Result 4536 states and 6277 transitions. [2023-02-16 02:07:38,118 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2023-02-16 02:07:38,119 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 7.714285714285714) internal successors, (108), 14 states have internal predecessors, (108), 14 states have call successors, (36), 2 states have call predecessors, (36), 2 states have return successors, (35), 14 states have call predecessors, (35), 14 states have call successors, (35) Word has length 183 [2023-02-16 02:07:38,119 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:38,133 INFO L225 Difference]: With dead ends: 4536 [2023-02-16 02:07:38,133 INFO L226 Difference]: Without dead ends: 3776 [2023-02-16 02:07:38,136 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 414 GetRequests, 377 SyntacticMatches, 0 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 265 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=385, Invalid=1097, Unknown=0, NotChecked=0, Total=1482 [2023-02-16 02:07:38,136 INFO L413 NwaCegarLoop]: 161 mSDtfsCounter, 197 mSDsluCounter, 552 mSDsCounter, 0 mSdLazyCounter, 706 mSolverCounterSat, 108 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 202 SdHoareTripleChecker+Valid, 713 SdHoareTripleChecker+Invalid, 814 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 108 IncrementalHoareTripleChecker+Valid, 706 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:38,137 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [202 Valid, 713 Invalid, 814 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [108 Valid, 706 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-02-16 02:07:38,140 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3776 states. [2023-02-16 02:07:38,867 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3776 to 3047. [2023-02-16 02:07:38,872 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3047 states, 2301 states have (on average 1.1899174272055628) internal successors, (2738), 2348 states have internal predecessors, (2738), 700 states have call successors, (700), 46 states have call predecessors, (700), 45 states have return successors, (699), 652 states have call predecessors, (699), 699 states have call successors, (699) [2023-02-16 02:07:38,878 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3047 states to 3047 states and 4137 transitions. [2023-02-16 02:07:38,878 INFO L78 Accepts]: Start accepts. Automaton has 3047 states and 4137 transitions. Word has length 183 [2023-02-16 02:07:38,879 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:38,879 INFO L495 AbstractCegarLoop]: Abstraction has 3047 states and 4137 transitions. [2023-02-16 02:07:38,879 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 7.714285714285714) internal successors, (108), 14 states have internal predecessors, (108), 14 states have call successors, (36), 2 states have call predecessors, (36), 2 states have return successors, (35), 14 states have call predecessors, (35), 14 states have call successors, (35) [2023-02-16 02:07:38,879 INFO L276 IsEmpty]: Start isEmpty. Operand 3047 states and 4137 transitions. [2023-02-16 02:07:38,889 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2023-02-16 02:07:38,889 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:38,890 INFO L195 NwaCegarLoop]: trace histogram [21, 20, 20, 11, 10, 10, 10, 7, 7, 6, 6, 6, 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-16 02:07:38,899 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-16 02:07:39,095 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-16 02:07:39,095 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:39,095 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:39,095 INFO L85 PathProgramCache]: Analyzing trace with hash 144972548, now seen corresponding path program 8 times [2023-02-16 02:07:39,095 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:39,095 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1369849425] [2023-02-16 02:07:39,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:39,096 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:39,102 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:39,102 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1269566925] [2023-02-16 02:07:39,103 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-16 02:07:39,103 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:39,103 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:39,104 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-16 02:07:39,107 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-16 02:07:39,180 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-16 02:07:39,180 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 02:07:39,182 INFO L263 TraceCheckSpWp]: Trace formula consists of 419 conjuncts, 16 conjunts are in the unsatisfiable core [2023-02-16 02:07:39,184 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 02:07:39,317 INFO L134 CoverageAnalysis]: Checked inductivity of 1108 backedges. 80 proven. 252 refuted. 0 times theorem prover too weak. 776 trivial. 0 not checked. [2023-02-16 02:07:39,317 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 02:07:39,584 INFO L134 CoverageAnalysis]: Checked inductivity of 1108 backedges. 80 proven. 252 refuted. 0 times theorem prover too weak. 776 trivial. 0 not checked. [2023-02-16 02:07:39,584 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 02:07:39,584 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1369849425] [2023-02-16 02:07:39,584 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 02:07:39,585 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1269566925] [2023-02-16 02:07:39,585 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1269566925] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 02:07:39,585 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 02:07:39,585 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 20 [2023-02-16 02:07:39,585 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [808656799] [2023-02-16 02:07:39,585 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 02:07:39,586 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2023-02-16 02:07:39,586 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 02:07:39,586 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2023-02-16 02:07:39,587 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=330, Unknown=0, NotChecked=0, Total=380 [2023-02-16 02:07:39,587 INFO L87 Difference]: Start difference. First operand 3047 states and 4137 transitions. Second operand has 20 states, 20 states have (on average 6.25) internal successors, (125), 20 states have internal predecessors, (125), 20 states have call successors, (37), 2 states have call predecessors, (37), 1 states have return successors, (36), 19 states have call predecessors, (36), 19 states have call successors, (36) [2023-02-16 02:07:44,727 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 02:07:44,727 INFO L93 Difference]: Finished difference Result 7412 states and 10306 transitions. [2023-02-16 02:07:44,727 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 86 states. [2023-02-16 02:07:44,727 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 6.25) internal successors, (125), 20 states have internal predecessors, (125), 20 states have call successors, (37), 2 states have call predecessors, (37), 1 states have return successors, (36), 19 states have call predecessors, (36), 19 states have call successors, (36) Word has length 183 [2023-02-16 02:07:44,728 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 02:07:44,751 INFO L225 Difference]: With dead ends: 7412 [2023-02-16 02:07:44,752 INFO L226 Difference]: Without dead ends: 6958 [2023-02-16 02:07:44,757 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 440 GetRequests, 346 SyntacticMatches, 0 SemanticMatches, 94 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2758 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=1198, Invalid=7922, Unknown=0, NotChecked=0, Total=9120 [2023-02-16 02:07:44,757 INFO L413 NwaCegarLoop]: 485 mSDtfsCounter, 366 mSDsluCounter, 3004 mSDsCounter, 0 mSdLazyCounter, 4599 mSolverCounterSat, 316 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 372 SdHoareTripleChecker+Valid, 3489 SdHoareTripleChecker+Invalid, 4915 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 316 IncrementalHoareTripleChecker+Valid, 4599 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2023-02-16 02:07:44,758 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [372 Valid, 3489 Invalid, 4915 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [316 Valid, 4599 Invalid, 0 Unknown, 0 Unchecked, 2.1s Time] [2023-02-16 02:07:44,763 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6958 states. [2023-02-16 02:07:46,047 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6958 to 5199. [2023-02-16 02:07:46,055 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5199 states, 3918 states have (on average 1.209800918836141) internal successors, (4740), 4013 states have internal predecessors, (4740), 1235 states have call successors, (1235), 46 states have call predecessors, (1235), 45 states have return successors, (1234), 1139 states have call predecessors, (1234), 1234 states have call successors, (1234) [2023-02-16 02:07:46,066 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5199 states to 5199 states and 7209 transitions. [2023-02-16 02:07:46,066 INFO L78 Accepts]: Start accepts. Automaton has 5199 states and 7209 transitions. Word has length 183 [2023-02-16 02:07:46,067 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 02:07:46,067 INFO L495 AbstractCegarLoop]: Abstraction has 5199 states and 7209 transitions. [2023-02-16 02:07:46,067 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 6.25) internal successors, (125), 20 states have internal predecessors, (125), 20 states have call successors, (37), 2 states have call predecessors, (37), 1 states have return successors, (36), 19 states have call predecessors, (36), 19 states have call successors, (36) [2023-02-16 02:07:46,067 INFO L276 IsEmpty]: Start isEmpty. Operand 5199 states and 7209 transitions. [2023-02-16 02:07:46,084 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2023-02-16 02:07:46,084 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 02:07:46,084 INFO L195 NwaCegarLoop]: trace histogram [21, 20, 20, 11, 10, 10, 10, 7, 7, 6, 6, 6, 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-16 02:07:46,090 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2023-02-16 02:07:46,289 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-16 02:07:46,290 INFO L420 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 02:07:46,290 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 02:07:46,290 INFO L85 PathProgramCache]: Analyzing trace with hash 1027204868, now seen corresponding path program 9 times [2023-02-16 02:07:46,290 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 02:07:46,291 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1291795192] [2023-02-16 02:07:46,291 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 02:07:46,291 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 02:07:46,305 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 02:07:46,305 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1021426244] [2023-02-16 02:07:46,305 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-16 02:07:46,306 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 02:07:46,306 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 02:07:46,307 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-16 02:07:46,310 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process