./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version a31fd051 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound50.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 5506d4c7458a400c41a33af3f6404f1e04b9f2e97e99f1fb53b74acf6bf59baf --- Real Ultimate output --- This is Ultimate 0.2.2-?-a31fd05 [2023-02-15 12:06:41,732 INFO L177 SettingsManager]: Resetting all preferences to default values... [2023-02-15 12:06:41,733 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2023-02-15 12:06:41,761 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2023-02-15 12:06:41,764 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2023-02-15 12:06:41,765 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2023-02-15 12:06:41,766 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2023-02-15 12:06:41,767 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2023-02-15 12:06:41,768 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2023-02-15 12:06:41,768 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2023-02-15 12:06:41,770 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2023-02-15 12:06:41,773 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2023-02-15 12:06:41,773 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2023-02-15 12:06:41,776 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2023-02-15 12:06:41,778 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2023-02-15 12:06:41,780 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2023-02-15 12:06:41,781 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2023-02-15 12:06:41,783 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2023-02-15 12:06:41,786 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2023-02-15 12:06:41,787 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2023-02-15 12:06:41,790 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2023-02-15 12:06:41,791 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2023-02-15 12:06:41,791 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2023-02-15 12:06:41,792 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2023-02-15 12:06:41,794 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2023-02-15 12:06:41,796 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2023-02-15 12:06:41,797 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2023-02-15 12:06:41,797 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2023-02-15 12:06:41,798 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2023-02-15 12:06:41,799 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2023-02-15 12:06:41,799 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2023-02-15 12:06:41,799 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2023-02-15 12:06:41,800 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2023-02-15 12:06:41,801 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2023-02-15 12:06:41,802 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2023-02-15 12:06:41,803 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2023-02-15 12:06:41,803 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2023-02-15 12:06:41,804 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2023-02-15 12:06:41,804 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2023-02-15 12:06:41,805 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2023-02-15 12:06:41,805 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2023-02-15 12:06:41,806 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2023-02-15 12:06:41,824 INFO L113 SettingsManager]: Loading preferences was successful [2023-02-15 12:06:41,824 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2023-02-15 12:06:41,824 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-02-15 12:06:41,824 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-02-15 12:06:41,825 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-02-15 12:06:41,825 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-02-15 12:06:41,826 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-02-15 12:06:41,826 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2023-02-15 12:06:41,827 INFO L138 SettingsManager]: * Use SBE=true [2023-02-15 12:06:41,827 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-02-15 12:06:41,827 INFO L138 SettingsManager]: * sizeof long=4 [2023-02-15 12:06:41,828 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2023-02-15 12:06:41,828 INFO L138 SettingsManager]: * sizeof POINTER=4 [2023-02-15 12:06:41,828 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2023-02-15 12:06:41,828 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-02-15 12:06:41,828 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-02-15 12:06:41,828 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-02-15 12:06:41,828 INFO L138 SettingsManager]: * sizeof long double=12 [2023-02-15 12:06:41,829 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2023-02-15 12:06:41,829 INFO L138 SettingsManager]: * Use constant arrays=true [2023-02-15 12:06:41,829 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-02-15 12:06:41,829 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-02-15 12:06:41,829 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-02-15 12:06:41,829 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2023-02-15 12:06:41,829 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-02-15 12:06:41,830 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-02-15 12:06:41,830 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-02-15 12:06:41,830 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-02-15 12:06:41,830 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2023-02-15 12:06:41,831 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-02-15 12:06:41,831 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-02-15 12:06:41,831 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-02-15 12:06:41,831 INFO L138 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-02-15 12:06:41,831 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-02-15 12:06:41,831 INFO L138 SettingsManager]: * Independence relation used for large block encoding in concurrent analysis=SYNTACTIC [2023-02-15 12:06:41,832 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 -> 5506d4c7458a400c41a33af3f6404f1e04b9f2e97e99f1fb53b74acf6bf59baf [2023-02-15 12:06:42,040 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-02-15 12:06:42,062 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-02-15 12:06:42,063 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-02-15 12:06:42,064 INFO L271 PluginConnector]: Initializing CDTParser... [2023-02-15 12:06:42,064 INFO L275 PluginConnector]: CDTParser initialized [2023-02-15 12:06:42,065 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound50.c [2023-02-15 12:06:43,010 INFO L500 CDTParser]: Created temporary CDT project at NULL [2023-02-15 12:06:43,218 INFO L351 CDTParser]: Found 1 translation units. [2023-02-15 12:06:43,218 INFO L172 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound50.c [2023-02-15 12:06:43,224 INFO L394 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/36e5ae721/9668d2e885834ae28920d8b9de8712f1/FLAGf376775b3 [2023-02-15 12:06:43,234 INFO L402 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/36e5ae721/9668d2e885834ae28920d8b9de8712f1 [2023-02-15 12:06:43,236 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-02-15 12:06:43,237 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2023-02-15 12:06:43,237 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-02-15 12:06:43,237 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-02-15 12:06:43,240 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2023-02-15 12:06:43,240 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.02 12:06:43" (1/1) ... [2023-02-15 12:06:43,241 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@78e735c0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43, skipping insertion in model container [2023-02-15 12:06:43,241 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.02 12:06:43" (1/1) ... [2023-02-15 12:06:43,248 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2023-02-15 12:06:43,257 INFO L178 MainTranslator]: Built tables and reachable declarations [2023-02-15 12:06:43,337 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/hard2_unwindbound50.c[526,539] [2023-02-15 12:06:43,346 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-15 12:06:43,352 INFO L203 MainTranslator]: Completed pre-run [2023-02-15 12:06:43,359 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/hard2_unwindbound50.c[526,539] [2023-02-15 12:06:43,363 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-15 12:06:43,370 INFO L208 MainTranslator]: Completed translation [2023-02-15 12:06:43,371 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43 WrapperNode [2023-02-15 12:06:43,371 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-02-15 12:06:43,372 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-02-15 12:06:43,372 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-02-15 12:06:43,372 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2023-02-15 12:06:43,376 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43" (1/1) ... [2023-02-15 12:06:43,380 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43" (1/1) ... [2023-02-15 12:06:43,390 INFO L138 Inliner]: procedures = 14, calls = 22, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 69 [2023-02-15 12:06:43,390 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-02-15 12:06:43,390 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-02-15 12:06:43,391 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2023-02-15 12:06:43,391 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2023-02-15 12:06:43,396 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43" (1/1) ... [2023-02-15 12:06:43,396 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43" (1/1) ... [2023-02-15 12:06:43,397 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43" (1/1) ... [2023-02-15 12:06:43,397 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43" (1/1) ... [2023-02-15 12:06:43,399 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43" (1/1) ... [2023-02-15 12:06:43,401 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43" (1/1) ... [2023-02-15 12:06:43,402 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43" (1/1) ... [2023-02-15 12:06:43,402 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43" (1/1) ... [2023-02-15 12:06:43,406 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-02-15 12:06:43,406 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-02-15 12:06:43,407 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2023-02-15 12:06:43,407 INFO L275 PluginConnector]: RCFGBuilder initialized [2023-02-15 12:06:43,407 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43" (1/1) ... [2023-02-15 12:06:43,411 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-02-15 12:06:43,417 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:06:43,429 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-02-15 12:06:43,433 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-02-15 12:06:43,455 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-02-15 12:06:43,455 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-02-15 12:06:43,455 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-02-15 12:06:43,455 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-02-15 12:06:43,456 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-02-15 12:06:43,456 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-02-15 12:06:43,495 INFO L235 CfgBuilder]: Building ICFG [2023-02-15 12:06:43,496 INFO L261 CfgBuilder]: Building CFG for each procedure with an implementation [2023-02-15 12:06:43,625 INFO L276 CfgBuilder]: Performing block encoding [2023-02-15 12:06:43,642 INFO L295 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-02-15 12:06:43,643 INFO L300 CfgBuilder]: Removed 2 assume(true) statements. [2023-02-15 12:06:43,644 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.02 12:06:43 BoogieIcfgContainer [2023-02-15 12:06:43,644 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-02-15 12:06:43,658 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-02-15 12:06:43,658 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2023-02-15 12:06:43,660 INFO L275 PluginConnector]: TraceAbstraction initialized [2023-02-15 12:06:43,660 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.02 12:06:43" (1/3) ... [2023-02-15 12:06:43,660 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3f0c1606 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.02 12:06:43, skipping insertion in model container [2023-02-15 12:06:43,660 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 12:06:43" (2/3) ... [2023-02-15 12:06:43,661 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3f0c1606 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.02 12:06:43, skipping insertion in model container [2023-02-15 12:06:43,661 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.02 12:06:43" (3/3) ... [2023-02-15 12:06:43,661 INFO L112 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound50.c [2023-02-15 12:06:43,672 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-02-15 12:06:43,672 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-02-15 12:06:43,707 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-02-15 12:06:43,733 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;@d4150cc, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-02-15 12:06:43,733 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-02-15 12:06:43,736 INFO L276 IsEmpty]: Start isEmpty. Operand has 26 states, 16 states have (on average 1.5625) internal successors, (25), 17 states have internal predecessors, (25), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-02-15 12:06:43,741 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2023-02-15 12:06:43,741 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:06:43,741 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:06:43,742 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:06:43,748 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:06:43,749 INFO L85 PathProgramCache]: Analyzing trace with hash 643118537, now seen corresponding path program 1 times [2023-02-15 12:06:43,754 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:06:43,754 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1034931281] [2023-02-15 12:06:43,755 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:43,755 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:06:43,808 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:06:43,835 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:06:43,835 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1034931281] [2023-02-15 12:06:43,836 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-02-15 12:06:43,836 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1164613715] [2023-02-15 12:06:43,837 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:43,837 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:06:43,837 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:06:43,839 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:06:43,859 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-02-15 12:06:43,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:06:43,897 INFO L263 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 1 conjunts are in the unsatisfiable core [2023-02-15 12:06:43,899 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:06:43,912 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-15 12:06:43,912 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 12:06:43,912 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1164613715] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 12:06:43,912 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 12:06:43,913 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-02-15 12:06:43,914 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [886651159] [2023-02-15 12:06:43,914 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 12:06:43,917 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-02-15 12:06:43,917 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:06:43,932 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-02-15 12:06:43,933 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-02-15 12:06:43,934 INFO L87 Difference]: Start difference. First operand has 26 states, 16 states have (on average 1.5625) internal successors, (25), 17 states have internal predecessors, (25), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-02-15 12:06:43,948 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:06:43,948 INFO L93 Difference]: Finished difference Result 50 states and 83 transitions. [2023-02-15 12:06:43,949 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-02-15 12:06:43,949 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2023-02-15 12:06:43,950 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:06:43,954 INFO L225 Difference]: With dead ends: 50 [2023-02-15 12:06:43,954 INFO L226 Difference]: Without dead ends: 22 [2023-02-15 12:06:43,956 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-02-15 12:06:43,958 INFO L413 NwaCegarLoop]: 36 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, 36 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 12:06:43,958 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 12:06:43,969 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2023-02-15 12:06:43,979 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2023-02-15 12:06:43,980 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 14 states have internal predecessors, (19), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-02-15 12:06:43,981 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 32 transitions. [2023-02-15 12:06:43,982 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 32 transitions. Word has length 8 [2023-02-15 12:06:43,982 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:06:43,982 INFO L495 AbstractCegarLoop]: Abstraction has 22 states and 32 transitions. [2023-02-15 12:06:43,982 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-02-15 12:06:43,983 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 32 transitions. [2023-02-15 12:06:43,983 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2023-02-15 12:06:43,984 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:06:43,984 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:06:43,988 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-15 12:06:44,188 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-02-15 12:06:44,189 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:06:44,190 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:06:44,190 INFO L85 PathProgramCache]: Analyzing trace with hash 181060127, now seen corresponding path program 1 times [2023-02-15 12:06:44,190 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:06:44,190 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [436784999] [2023-02-15 12:06:44,190 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:44,190 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:06:44,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:06:44,347 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-15 12:06:44,347 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:06:44,347 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [436784999] [2023-02-15 12:06:44,347 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [436784999] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 12:06:44,347 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 12:06:44,347 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-02-15 12:06:44,347 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [280185915] [2023-02-15 12:06:44,347 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 12:06:44,348 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-15 12:06:44,348 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:06:44,349 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-15 12:06:44,349 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-02-15 12:06:44,349 INFO L87 Difference]: Start difference. First operand 22 states and 32 transitions. Second operand has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-02-15 12:06:44,404 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:06:44,404 INFO L93 Difference]: Finished difference Result 36 states and 51 transitions. [2023-02-15 12:06:44,405 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-15 12:06:44,405 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2023-02-15 12:06:44,405 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:06:44,406 INFO L225 Difference]: With dead ends: 36 [2023-02-15 12:06:44,406 INFO L226 Difference]: Without dead ends: 34 [2023-02-15 12:06:44,406 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-02-15 12:06:44,407 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 15 mSDsluCounter, 68 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 12:06:44,407 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 99 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 12:06:44,408 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2023-02-15 12:06:44,414 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 26. [2023-02-15 12:06:44,414 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-02-15 12:06:44,415 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 35 transitions. [2023-02-15 12:06:44,415 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 35 transitions. Word has length 8 [2023-02-15 12:06:44,415 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:06:44,415 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 35 transitions. [2023-02-15 12:06:44,415 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-02-15 12:06:44,415 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 35 transitions. [2023-02-15 12:06:44,415 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2023-02-15 12:06:44,415 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:06:44,415 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:06:44,416 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-02-15 12:06:44,416 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:06:44,416 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:06:44,416 INFO L85 PathProgramCache]: Analyzing trace with hash -712280900, now seen corresponding path program 1 times [2023-02-15 12:06:44,416 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:06:44,416 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [772631071] [2023-02-15 12:06:44,416 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:44,416 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:06:44,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:06:44,437 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:06:44,437 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [772631071] [2023-02-15 12:06:44,437 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-02-15 12:06:44,437 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2026432068] [2023-02-15 12:06:44,437 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:44,437 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:06:44,437 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:06:44,448 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:06:44,458 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-02-15 12:06:44,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:06:44,499 INFO L263 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 3 conjunts are in the unsatisfiable core [2023-02-15 12:06:44,500 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:06:44,535 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-15 12:06:44,536 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 12:06:44,536 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2026432068] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 12:06:44,536 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 12:06:44,536 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-02-15 12:06:44,536 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [774845343] [2023-02-15 12:06:44,537 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 12:06:44,538 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-02-15 12:06:44,538 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:06:44,539 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-02-15 12:06:44,539 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-02-15 12:06:44,539 INFO L87 Difference]: Start difference. First operand 26 states and 35 transitions. Second operand has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-02-15 12:06:44,563 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:06:44,564 INFO L93 Difference]: Finished difference Result 42 states and 57 transitions. [2023-02-15 12:06:44,564 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-02-15 12:06:44,565 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2023-02-15 12:06:44,565 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:06:44,566 INFO L225 Difference]: With dead ends: 42 [2023-02-15 12:06:44,566 INFO L226 Difference]: Without dead ends: 28 [2023-02-15 12:06:44,567 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-02-15 12:06:44,568 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 0 mSDsluCounter, 55 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 12:06:44,569 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 85 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 12:06:44,571 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2023-02-15 12:06:44,573 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2023-02-15 12:06:44,576 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-02-15 12:06:44,577 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2023-02-15 12:06:44,577 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 10 [2023-02-15 12:06:44,577 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:06:44,577 INFO L495 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2023-02-15 12:06:44,577 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-02-15 12:06:44,577 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2023-02-15 12:06:44,578 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2023-02-15 12:06:44,578 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:06:44,578 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:06:44,584 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-02-15 12:06:44,784 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2023-02-15 12:06:44,784 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:06:44,785 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:06:44,785 INFO L85 PathProgramCache]: Analyzing trace with hash 2036073049, now seen corresponding path program 1 times [2023-02-15 12:06:44,785 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:06:44,785 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1388744486] [2023-02-15 12:06:44,785 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:44,785 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:06:44,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:06:44,871 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-02-15 12:06:44,873 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:06:44,877 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-02-15 12:06:44,881 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:06:44,881 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1388744486] [2023-02-15 12:06:44,881 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1388744486] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 12:06:44,881 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 12:06:44,881 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-02-15 12:06:44,881 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [395044552] [2023-02-15 12:06:44,882 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 12:06:44,882 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-15 12:06:44,882 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:06:44,883 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-15 12:06:44,886 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-02-15 12:06:44,886 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-02-15 12:06:44,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:06:44,925 INFO L93 Difference]: Finished difference Result 42 states and 56 transitions. [2023-02-15 12:06:44,925 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-15 12:06:44,925 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 13 [2023-02-15 12:06:44,926 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:06:44,926 INFO L225 Difference]: With dead ends: 42 [2023-02-15 12:06:44,926 INFO L226 Difference]: Without dead ends: 40 [2023-02-15 12:06:44,926 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-02-15 12:06:44,927 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 13 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 12:06:44,927 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 95 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 12:06:44,928 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2023-02-15 12:06:44,931 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 32. [2023-02-15 12:06:44,931 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-02-15 12:06:44,932 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 40 transitions. [2023-02-15 12:06:44,932 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 40 transitions. Word has length 13 [2023-02-15 12:06:44,932 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:06:44,932 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 40 transitions. [2023-02-15 12:06:44,932 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-02-15 12:06:44,932 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 40 transitions. [2023-02-15 12:06:44,933 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2023-02-15 12:06:44,933 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:06:44,933 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:06:44,933 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-02-15 12:06:44,934 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:06:44,934 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:06:44,934 INFO L85 PathProgramCache]: Analyzing trace with hash 380169759, now seen corresponding path program 1 times [2023-02-15 12:06:44,934 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:06:44,934 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [715826833] [2023-02-15 12:06:44,934 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:44,935 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:06:44,941 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:06:44,941 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [529032341] [2023-02-15 12:06:44,942 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:44,942 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:06:44,942 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:06:44,943 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:06:44,988 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-02-15 12:06:44,991 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:06:44,992 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 19 conjunts are in the unsatisfiable core [2023-02-15 12:06:44,993 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:06:45,057 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-02-15 12:06:45,058 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:06:45,183 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-02-15 12:06:45,183 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:06:45,183 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [715826833] [2023-02-15 12:06:45,183 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:06:45,183 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [529032341] [2023-02-15 12:06:45,183 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [529032341] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:06:45,183 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:06:45,183 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 12 [2023-02-15 12:06:45,183 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1280728023] [2023-02-15 12:06:45,183 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:06:45,184 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-02-15 12:06:45,184 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:06:45,184 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-02-15 12:06:45,184 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2023-02-15 12:06:45,184 INFO L87 Difference]: Start difference. First operand 32 states and 40 transitions. Second operand has 12 states, 10 states have (on average 2.0) internal successors, (20), 9 states have internal predecessors, (20), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-15 12:06:45,442 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:06:45,442 INFO L93 Difference]: Finished difference Result 71 states and 96 transitions. [2023-02-15 12:06:45,443 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-02-15 12:06:45,443 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 2.0) internal successors, (20), 9 states have internal predecessors, (20), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) Word has length 18 [2023-02-15 12:06:45,443 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:06:45,444 INFO L225 Difference]: With dead ends: 71 [2023-02-15 12:06:45,444 INFO L226 Difference]: Without dead ends: 56 [2023-02-15 12:06:45,445 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2023-02-15 12:06:45,445 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 42 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 145 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 79 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 145 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-02-15 12:06:45,446 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 79 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 145 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-02-15 12:06:45,446 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2023-02-15 12:06:45,454 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 54. [2023-02-15 12:06:45,454 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 33 states have (on average 1.2727272727272727) internal successors, (42), 36 states have internal predecessors, (42), 15 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2023-02-15 12:06:45,460 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2023-02-15 12:06:45,462 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 70 transitions. Word has length 18 [2023-02-15 12:06:45,462 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:06:45,462 INFO L495 AbstractCegarLoop]: Abstraction has 54 states and 70 transitions. [2023-02-15 12:06:45,462 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 2.0) internal successors, (20), 9 states have internal predecessors, (20), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-15 12:06:45,462 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 70 transitions. [2023-02-15 12:06:45,463 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2023-02-15 12:06:45,463 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:06:45,463 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:06:45,470 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-02-15 12:06:45,668 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:06:45,668 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:06:45,669 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:06:45,669 INFO L85 PathProgramCache]: Analyzing trace with hash -461064832, now seen corresponding path program 1 times [2023-02-15 12:06:45,669 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:06:45,669 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [423434440] [2023-02-15 12:06:45,669 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:45,669 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:06:45,677 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:06:45,677 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1701264499] [2023-02-15 12:06:45,677 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:45,677 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:06:45,677 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:06:45,680 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:06:45,682 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-02-15 12:06:45,729 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:06:45,730 INFO L263 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 17 conjunts are in the unsatisfiable core [2023-02-15 12:06:45,731 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:06:45,799 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-02-15 12:06:45,800 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:06:45,901 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-02-15 12:06:45,901 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:06:45,901 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [423434440] [2023-02-15 12:06:45,902 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:06:45,902 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1701264499] [2023-02-15 12:06:45,902 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1701264499] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:06:45,902 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:06:45,902 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 11 [2023-02-15 12:06:45,902 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1252620282] [2023-02-15 12:06:45,902 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:06:45,903 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-02-15 12:06:45,903 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:06:45,903 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-02-15 12:06:45,903 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2023-02-15 12:06:45,903 INFO L87 Difference]: Start difference. First operand 54 states and 70 transitions. Second operand has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (8), 3 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2023-02-15 12:06:46,008 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:06:46,009 INFO L93 Difference]: Finished difference Result 73 states and 97 transitions. [2023-02-15 12:06:46,009 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-02-15 12:06:46,009 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (8), 3 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 26 [2023-02-15 12:06:46,010 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:06:46,010 INFO L225 Difference]: With dead ends: 73 [2023-02-15 12:06:46,010 INFO L226 Difference]: Without dead ends: 65 [2023-02-15 12:06:46,011 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2023-02-15 12:06:46,011 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 29 mSDsluCounter, 52 mSDsCounter, 0 mSdLazyCounter, 124 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 140 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 124 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 12:06:46,011 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 71 Invalid, 140 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 124 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 12:06:46,012 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2023-02-15 12:06:46,018 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 62. [2023-02-15 12:06:46,018 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 39 states have (on average 1.2820512820512822) internal successors, (50), 43 states have internal predecessors, (50), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 12 states have call predecessors, (15), 15 states have call successors, (15) [2023-02-15 12:06:46,019 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 81 transitions. [2023-02-15 12:06:46,019 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 81 transitions. Word has length 26 [2023-02-15 12:06:46,019 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:06:46,019 INFO L495 AbstractCegarLoop]: Abstraction has 62 states and 81 transitions. [2023-02-15 12:06:46,019 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (8), 3 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2023-02-15 12:06:46,019 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 81 transitions. [2023-02-15 12:06:46,020 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2023-02-15 12:06:46,020 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:06:46,020 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:06:46,036 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-02-15 12:06:46,224 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:06:46,225 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:06:46,225 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:06:46,225 INFO L85 PathProgramCache]: Analyzing trace with hash 847666457, now seen corresponding path program 1 times [2023-02-15 12:06:46,225 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:06:46,225 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1462106969] [2023-02-15 12:06:46,226 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:46,226 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:06:46,233 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:06:46,238 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [624123135] [2023-02-15 12:06:46,238 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:46,239 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:06:46,239 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:06:46,240 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:06:46,246 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-02-15 12:06:46,277 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:06:46,277 INFO L263 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 5 conjunts are in the unsatisfiable core [2023-02-15 12:06:46,278 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:06:46,312 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-02-15 12:06:46,312 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:06:46,344 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-02-15 12:06:46,344 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:06:46,344 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1462106969] [2023-02-15 12:06:46,344 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:06:46,344 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [624123135] [2023-02-15 12:06:46,344 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [624123135] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:06:46,344 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:06:46,345 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2023-02-15 12:06:46,345 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1662572895] [2023-02-15 12:06:46,345 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:06:46,345 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-02-15 12:06:46,345 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:06:46,346 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-02-15 12:06:46,346 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2023-02-15 12:06:46,346 INFO L87 Difference]: Start difference. First operand 62 states and 81 transitions. Second operand has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2023-02-15 12:06:46,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:06:46,435 INFO L93 Difference]: Finished difference Result 165 states and 205 transitions. [2023-02-15 12:06:46,435 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-02-15 12:06:46,435 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 33 [2023-02-15 12:06:46,435 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:06:46,436 INFO L225 Difference]: With dead ends: 165 [2023-02-15 12:06:46,436 INFO L226 Difference]: Without dead ends: 127 [2023-02-15 12:06:46,437 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 58 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2023-02-15 12:06:46,437 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 34 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 137 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 12:06:46,437 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 137 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 12:06:46,438 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2023-02-15 12:06:46,455 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 121. [2023-02-15 12:06:46,455 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 79 states have (on average 1.1898734177215189) internal successors, (94), 83 states have internal predecessors, (94), 26 states have call successors, (26), 16 states have call predecessors, (26), 15 states have return successors, (24), 21 states have call predecessors, (24), 24 states have call successors, (24) [2023-02-15 12:06:46,456 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 144 transitions. [2023-02-15 12:06:46,456 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 144 transitions. Word has length 33 [2023-02-15 12:06:46,456 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:06:46,456 INFO L495 AbstractCegarLoop]: Abstraction has 121 states and 144 transitions. [2023-02-15 12:06:46,456 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2023-02-15 12:06:46,456 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 144 transitions. [2023-02-15 12:06:46,457 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2023-02-15 12:06:46,457 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:06:46,457 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:06:46,464 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-02-15 12:06:46,662 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:06:46,662 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:06:46,662 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:06:46,662 INFO L85 PathProgramCache]: Analyzing trace with hash 1605675221, now seen corresponding path program 1 times [2023-02-15 12:06:46,663 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:06:46,663 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [305280109] [2023-02-15 12:06:46,663 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:46,663 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:06:46,669 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:06:46,669 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [154630099] [2023-02-15 12:06:46,669 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:46,669 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:06:46,669 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:06:46,670 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:06:46,672 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-02-15 12:06:46,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:06:46,710 INFO L263 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-15 12:06:46,715 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:06:46,776 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 36 proven. 42 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2023-02-15 12:06:46,776 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:06:46,834 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-02-15 12:06:46,835 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:06:46,835 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [305280109] [2023-02-15 12:06:46,835 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:06:46,835 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [154630099] [2023-02-15 12:06:46,835 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [154630099] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:06:46,835 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:06:46,835 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 10 [2023-02-15 12:06:46,836 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1724787336] [2023-02-15 12:06:46,836 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:06:46,836 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-02-15 12:06:46,836 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:06:46,837 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-02-15 12:06:46,837 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2023-02-15 12:06:46,837 INFO L87 Difference]: Start difference. First operand 121 states and 144 transitions. Second operand has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2023-02-15 12:06:46,948 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:06:46,949 INFO L93 Difference]: Finished difference Result 249 states and 307 transitions. [2023-02-15 12:06:46,949 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-02-15 12:06:46,949 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) Word has length 49 [2023-02-15 12:06:46,949 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:06:46,951 INFO L225 Difference]: With dead ends: 249 [2023-02-15 12:06:46,951 INFO L226 Difference]: Without dead ends: 228 [2023-02-15 12:06:46,951 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 88 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=52, Invalid=104, Unknown=0, NotChecked=0, Total=156 [2023-02-15 12:06:46,952 INFO L413 NwaCegarLoop]: 55 mSDtfsCounter, 80 mSDsluCounter, 206 mSDsCounter, 0 mSdLazyCounter, 102 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 80 SdHoareTripleChecker+Valid, 261 SdHoareTripleChecker+Invalid, 117 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 102 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 12:06:46,952 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [80 Valid, 261 Invalid, 117 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 102 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 12:06:46,953 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 228 states. [2023-02-15 12:06:46,970 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 228 to 221. [2023-02-15 12:06:46,971 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 221 states, 144 states have (on average 1.1944444444444444) internal successors, (172), 155 states have internal predecessors, (172), 51 states have call successors, (51), 26 states have call predecessors, (51), 25 states have return successors, (47), 39 states have call predecessors, (47), 47 states have call successors, (47) [2023-02-15 12:06:46,972 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 221 states to 221 states and 270 transitions. [2023-02-15 12:06:46,973 INFO L78 Accepts]: Start accepts. Automaton has 221 states and 270 transitions. Word has length 49 [2023-02-15 12:06:46,973 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:06:46,973 INFO L495 AbstractCegarLoop]: Abstraction has 221 states and 270 transitions. [2023-02-15 12:06:46,973 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2023-02-15 12:06:46,973 INFO L276 IsEmpty]: Start isEmpty. Operand 221 states and 270 transitions. [2023-02-15 12:06:46,974 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2023-02-15 12:06:46,974 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:06:46,975 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:06:46,982 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-02-15 12:06:47,179 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:06:47,180 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:06:47,180 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:06:47,180 INFO L85 PathProgramCache]: Analyzing trace with hash -1800695307, now seen corresponding path program 1 times [2023-02-15 12:06:47,180 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:06:47,181 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1432971737] [2023-02-15 12:06:47,181 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:47,181 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:06:47,187 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:06:47,188 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [42676944] [2023-02-15 12:06:47,188 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:47,188 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:06:47,188 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:06:47,189 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:06:47,191 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-02-15 12:06:47,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:06:47,243 INFO L263 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 33 conjunts are in the unsatisfiable core [2023-02-15 12:06:47,245 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:06:47,467 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 18 proven. 28 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-02-15 12:06:47,468 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:06:48,093 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 18 proven. 28 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-02-15 12:06:48,093 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:06:48,093 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1432971737] [2023-02-15 12:06:48,094 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:06:48,094 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [42676944] [2023-02-15 12:06:48,094 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [42676944] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:06:48,094 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:06:48,094 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-02-15 12:06:48,094 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [49958574] [2023-02-15 12:06:48,094 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:06:48,095 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-02-15 12:06:48,095 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:06:48,095 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-02-15 12:06:48,095 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2023-02-15 12:06:48,096 INFO L87 Difference]: Start difference. First operand 221 states and 270 transitions. Second operand has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 14 states have internal predecessors, (40), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2023-02-15 12:06:53,722 WARN L233 SmtUtils]: Spent 5.51s on a formula simplification. DAG size of input: 48 DAG size of output: 46 (called from [L 361] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-02-15 12:06:55,602 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.43s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 12:06:55,849 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:06:55,849 INFO L93 Difference]: Finished difference Result 372 states and 479 transitions. [2023-02-15 12:06:55,850 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-02-15 12:06:55,850 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 14 states have internal predecessors, (40), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 58 [2023-02-15 12:06:55,851 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:06:55,852 INFO L225 Difference]: With dead ends: 372 [2023-02-15 12:06:55,852 INFO L226 Difference]: Without dead ends: 299 [2023-02-15 12:06:55,853 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 5.7s TimeCoverageRelationStatistics Valid=83, Invalid=297, Unknown=0, NotChecked=0, Total=380 [2023-02-15 12:06:55,853 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 60 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 409 mSolverCounterSat, 95 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 66 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 504 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 95 IncrementalHoareTripleChecker+Valid, 409 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2023-02-15 12:06:55,853 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [66 Valid, 147 Invalid, 504 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [95 Valid, 409 Invalid, 0 Unknown, 0 Unchecked, 2.1s Time] [2023-02-15 12:06:55,854 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 299 states. [2023-02-15 12:06:55,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 299 to 272. [2023-02-15 12:06:55,920 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 272 states, 186 states have (on average 1.2258064516129032) internal successors, (228), 194 states have internal predecessors, (228), 56 states have call successors, (56), 29 states have call predecessors, (56), 29 states have return successors, (54), 48 states have call predecessors, (54), 54 states have call successors, (54) [2023-02-15 12:06:55,924 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 272 states to 272 states and 338 transitions. [2023-02-15 12:06:55,924 INFO L78 Accepts]: Start accepts. Automaton has 272 states and 338 transitions. Word has length 58 [2023-02-15 12:06:55,925 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:06:55,940 INFO L495 AbstractCegarLoop]: Abstraction has 272 states and 338 transitions. [2023-02-15 12:06:55,941 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 14 states have internal predecessors, (40), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2023-02-15 12:06:55,941 INFO L276 IsEmpty]: Start isEmpty. Operand 272 states and 338 transitions. [2023-02-15 12:06:55,946 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2023-02-15 12:06:55,947 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:06:55,947 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:06:55,954 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-02-15 12:06:56,147 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:06:56,148 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:06:56,148 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:06:56,148 INFO L85 PathProgramCache]: Analyzing trace with hash -1688778742, now seen corresponding path program 1 times [2023-02-15 12:06:56,148 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:06:56,148 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [843136244] [2023-02-15 12:06:56,148 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:56,149 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:06:56,154 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:06:56,154 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1166169092] [2023-02-15 12:06:56,154 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:06:56,154 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:06:56,154 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:06:56,163 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:06:56,167 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-02-15 12:06:56,209 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:06:56,210 INFO L263 TraceCheckSpWp]: Trace formula consists of 192 conjuncts, 35 conjunts are in the unsatisfiable core [2023-02-15 12:06:56,212 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:06:56,400 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 22 proven. 36 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-02-15 12:06:56,400 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:06:56,805 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 22 proven. 36 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-02-15 12:06:56,806 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:06:56,806 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [843136244] [2023-02-15 12:06:56,806 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:06:56,806 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1166169092] [2023-02-15 12:06:56,806 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1166169092] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:06:56,806 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:06:56,806 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2023-02-15 12:06:56,808 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1884365919] [2023-02-15 12:06:56,808 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:06:56,809 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-02-15 12:06:56,809 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:06:56,810 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-02-15 12:06:56,810 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=187, Unknown=0, NotChecked=0, Total=240 [2023-02-15 12:06:56,811 INFO L87 Difference]: Start difference. First operand 272 states and 338 transitions. Second operand has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2023-02-15 12:06:58,820 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.62s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 12:07:00,623 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.55s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 12:07:00,668 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:07:00,668 INFO L93 Difference]: Finished difference Result 341 states and 423 transitions. [2023-02-15 12:07:00,668 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-02-15 12:07:00,668 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) Word has length 69 [2023-02-15 12:07:00,669 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:07:00,670 INFO L225 Difference]: With dead ends: 341 [2023-02-15 12:07:00,670 INFO L226 Difference]: Without dead ends: 260 [2023-02-15 12:07:00,670 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 140 GetRequests, 121 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=86, Invalid=294, Unknown=0, NotChecked=0, Total=380 [2023-02-15 12:07:00,671 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 36 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 343 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 395 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 343 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.6s IncrementalHoareTripleChecker+Time [2023-02-15 12:07:00,671 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 111 Invalid, 395 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 343 Invalid, 0 Unknown, 0 Unchecked, 3.6s Time] [2023-02-15 12:07:00,671 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 260 states. [2023-02-15 12:07:00,746 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 260 to 236. [2023-02-15 12:07:00,747 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 236 states, 161 states have (on average 1.1801242236024845) internal successors, (190), 165 states have internal predecessors, (190), 46 states have call successors, (46), 29 states have call predecessors, (46), 28 states have return successors, (44), 41 states have call predecessors, (44), 44 states have call successors, (44) [2023-02-15 12:07:00,748 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 236 states to 236 states and 280 transitions. [2023-02-15 12:07:00,748 INFO L78 Accepts]: Start accepts. Automaton has 236 states and 280 transitions. Word has length 69 [2023-02-15 12:07:00,748 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:07:00,748 INFO L495 AbstractCegarLoop]: Abstraction has 236 states and 280 transitions. [2023-02-15 12:07:00,749 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2023-02-15 12:07:00,749 INFO L276 IsEmpty]: Start isEmpty. Operand 236 states and 280 transitions. [2023-02-15 12:07:00,750 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2023-02-15 12:07:00,750 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:07:00,750 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:07:00,765 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-02-15 12:07:00,951 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,SelfDestructingSolverStorable9 [2023-02-15 12:07:00,951 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:07:00,951 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:07:00,951 INFO L85 PathProgramCache]: Analyzing trace with hash -428937714, now seen corresponding path program 1 times [2023-02-15 12:07:00,951 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:07:00,951 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [679558183] [2023-02-15 12:07:00,951 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:07:00,952 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:07:00,957 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:07:00,957 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1050831571] [2023-02-15 12:07:00,957 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:07:00,957 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:07:00,957 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:07:00,977 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:07:00,997 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-02-15 12:07:01,049 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:07:01,050 INFO L263 TraceCheckSpWp]: Trace formula consists of 201 conjuncts, 29 conjunts are in the unsatisfiable core [2023-02-15 12:07:01,052 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:07:01,172 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 24 proven. 39 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2023-02-15 12:07:01,172 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:07:01,450 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 24 proven. 39 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2023-02-15 12:07:01,451 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:07:01,451 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [679558183] [2023-02-15 12:07:01,451 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:07:01,451 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1050831571] [2023-02-15 12:07:01,451 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1050831571] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:07:01,451 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:07:01,451 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2023-02-15 12:07:01,452 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1321465862] [2023-02-15 12:07:01,452 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:07:01,452 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-02-15 12:07:01,453 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:07:01,453 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-02-15 12:07:01,453 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2023-02-15 12:07:01,453 INFO L87 Difference]: Start difference. First operand 236 states and 280 transitions. Second operand has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2023-02-15 12:07:01,900 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:07:01,901 INFO L93 Difference]: Finished difference Result 260 states and 307 transitions. [2023-02-15 12:07:01,907 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-02-15 12:07:01,907 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) Word has length 74 [2023-02-15 12:07:01,909 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:07:01,912 INFO L225 Difference]: With dead ends: 260 [2023-02-15 12:07:01,912 INFO L226 Difference]: Without dead ends: 215 [2023-02-15 12:07:01,913 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 132 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=86, Invalid=294, Unknown=0, NotChecked=0, Total=380 [2023-02-15 12:07:01,913 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 25 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 395 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 165 SdHoareTripleChecker+Invalid, 429 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 395 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-02-15 12:07:01,914 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 165 Invalid, 429 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 395 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-02-15 12:07:01,914 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2023-02-15 12:07:01,939 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 210. [2023-02-15 12:07:01,940 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 210 states, 143 states have (on average 1.1468531468531469) internal successors, (164), 148 states have internal predecessors, (164), 41 states have call successors, (41), 25 states have call predecessors, (41), 25 states have return successors, (39), 36 states have call predecessors, (39), 39 states have call successors, (39) [2023-02-15 12:07:01,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 210 states to 210 states and 244 transitions. [2023-02-15 12:07:01,941 INFO L78 Accepts]: Start accepts. Automaton has 210 states and 244 transitions. Word has length 74 [2023-02-15 12:07:01,941 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:07:01,941 INFO L495 AbstractCegarLoop]: Abstraction has 210 states and 244 transitions. [2023-02-15 12:07:01,941 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2023-02-15 12:07:01,941 INFO L276 IsEmpty]: Start isEmpty. Operand 210 states and 244 transitions. [2023-02-15 12:07:01,942 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2023-02-15 12:07:01,942 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:07:01,942 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2023-02-15 12:07:01,951 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-02-15 12:07:02,146 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:07:02,147 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:07:02,147 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:07:02,147 INFO L85 PathProgramCache]: Analyzing trace with hash 1611798954, now seen corresponding path program 2 times [2023-02-15 12:07:02,147 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:07:02,147 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [548234716] [2023-02-15 12:07:02,148 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:07:02,148 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:07:02,153 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:07:02,154 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1690717044] [2023-02-15 12:07:02,154 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-15 12:07:02,154 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:07:02,154 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:07:02,165 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:07:02,166 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-02-15 12:07:02,245 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-15 12:07:02,245 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:07:02,246 INFO L263 TraceCheckSpWp]: Trace formula consists of 242 conjuncts, 46 conjunts are in the unsatisfiable core [2023-02-15 12:07:02,250 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:07:02,527 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 28 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2023-02-15 12:07:02,528 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:07:31,021 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 28 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2023-02-15 12:07:31,021 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:07:31,021 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [548234716] [2023-02-15 12:07:31,021 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:07:31,021 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1690717044] [2023-02-15 12:07:31,021 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1690717044] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:07:31,021 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:07:31,022 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 21 [2023-02-15 12:07:31,022 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1989082726] [2023-02-15 12:07:31,022 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:07:31,022 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-02-15 12:07:31,022 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:07:31,023 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-02-15 12:07:31,023 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=336, Unknown=2, NotChecked=0, Total=420 [2023-02-15 12:07:31,024 INFO L87 Difference]: Start difference. First operand 210 states and 244 transitions. Second operand has 21 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 19 states have internal predecessors, (54), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) [2023-02-15 12:07:56,969 WARN L233 SmtUtils]: Spent 25.11s on a formula simplification. DAG size of input: 172 DAG size of output: 104 (called from [L 361] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-02-15 12:08:04,367 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:08:04,368 INFO L93 Difference]: Finished difference Result 306 states and 390 transitions. [2023-02-15 12:08:04,368 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-02-15 12:08:04,368 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 19 states have internal predecessors, (54), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) Word has length 90 [2023-02-15 12:08:04,368 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:08:04,369 INFO L225 Difference]: With dead ends: 306 [2023-02-15 12:08:04,369 INFO L226 Difference]: Without dead ends: 262 [2023-02-15 12:08:04,370 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 158 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 53 ImplicationChecksByTransitivity, 36.1s TimeCoverageRelationStatistics Valid=151, Invalid=549, Unknown=2, NotChecked=0, Total=702 [2023-02-15 12:08:04,370 INFO L413 NwaCegarLoop]: 54 mSDtfsCounter, 115 mSDsluCounter, 274 mSDsCounter, 0 mSdLazyCounter, 1063 mSolverCounterSat, 143 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 124 SdHoareTripleChecker+Valid, 328 SdHoareTripleChecker+Invalid, 1206 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 143 IncrementalHoareTripleChecker+Valid, 1063 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.7s IncrementalHoareTripleChecker+Time [2023-02-15 12:08:04,370 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [124 Valid, 328 Invalid, 1206 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [143 Valid, 1063 Invalid, 0 Unknown, 0 Unchecked, 5.7s Time] [2023-02-15 12:08:04,371 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 262 states. [2023-02-15 12:08:04,425 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 262 to 247. [2023-02-15 12:08:04,426 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 247 states, 166 states have (on average 1.1987951807228916) internal successors, (199), 175 states have internal predecessors, (199), 54 states have call successors, (54), 26 states have call predecessors, (54), 26 states have return successors, (52), 45 states have call predecessors, (52), 52 states have call successors, (52) [2023-02-15 12:08:04,427 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 247 states to 247 states and 305 transitions. [2023-02-15 12:08:04,427 INFO L78 Accepts]: Start accepts. Automaton has 247 states and 305 transitions. Word has length 90 [2023-02-15 12:08:04,427 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:08:04,427 INFO L495 AbstractCegarLoop]: Abstraction has 247 states and 305 transitions. [2023-02-15 12:08:04,428 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 19 states have internal predecessors, (54), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) [2023-02-15 12:08:04,428 INFO L276 IsEmpty]: Start isEmpty. Operand 247 states and 305 transitions. [2023-02-15 12:08:04,428 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2023-02-15 12:08:04,428 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:08:04,429 INFO L195 NwaCegarLoop]: trace histogram [15, 14, 14, 5, 4, 4, 4, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:08:04,437 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-02-15 12:08:04,633 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,SelfDestructingSolverStorable11 [2023-02-15 12:08:04,634 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:08:04,634 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:08:04,634 INFO L85 PathProgramCache]: Analyzing trace with hash 1991126182, now seen corresponding path program 1 times [2023-02-15 12:08:04,634 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:08:04,635 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [93066016] [2023-02-15 12:08:04,635 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:08:04,635 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:08:04,641 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:08:04,641 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [673485203] [2023-02-15 12:08:04,641 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:08:04,641 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:08:04,641 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:08:04,642 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:08:04,644 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-02-15 12:08:04,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:08:04,690 INFO L263 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 11 conjunts are in the unsatisfiable core [2023-02-15 12:08:04,692 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:08:04,781 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 120 proven. 260 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2023-02-15 12:08:04,782 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:08:04,879 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 28 proven. 44 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2023-02-15 12:08:04,879 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:08:04,879 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [93066016] [2023-02-15 12:08:04,880 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:08:04,880 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [673485203] [2023-02-15 12:08:04,880 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [673485203] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:08:04,880 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:08:04,880 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 14 [2023-02-15 12:08:04,880 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [885921021] [2023-02-15 12:08:04,880 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:08:04,881 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-02-15 12:08:04,881 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:08:04,881 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-02-15 12:08:04,881 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2023-02-15 12:08:04,882 INFO L87 Difference]: Start difference. First operand 247 states and 305 transitions. Second operand has 14 states, 14 states have (on average 4.071428571428571) internal successors, (57), 14 states have internal predecessors, (57), 9 states have call successors, (29), 6 states have call predecessors, (29), 6 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) [2023-02-15 12:08:05,216 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:08:05,217 INFO L93 Difference]: Finished difference Result 707 states and 937 transitions. [2023-02-15 12:08:05,217 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-02-15 12:08:05,217 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.071428571428571) internal successors, (57), 14 states have internal predecessors, (57), 9 states have call successors, (29), 6 states have call predecessors, (29), 6 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) Word has length 96 [2023-02-15 12:08:05,218 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:08:05,220 INFO L225 Difference]: With dead ends: 707 [2023-02-15 12:08:05,220 INFO L226 Difference]: Without dead ends: 629 [2023-02-15 12:08:05,220 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 199 GetRequests, 178 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2023-02-15 12:08:05,221 INFO L413 NwaCegarLoop]: 74 mSDtfsCounter, 163 mSDsluCounter, 219 mSDsCounter, 0 mSdLazyCounter, 204 mSolverCounterSat, 64 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 163 SdHoareTripleChecker+Valid, 293 SdHoareTripleChecker+Invalid, 268 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 64 IncrementalHoareTripleChecker+Valid, 204 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-02-15 12:08:05,221 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [163 Valid, 293 Invalid, 268 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [64 Valid, 204 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-02-15 12:08:05,222 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 629 states. [2023-02-15 12:08:05,348 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 629 to 549. [2023-02-15 12:08:05,349 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 549 states, 362 states have (on average 1.270718232044199) internal successors, (460), 391 states have internal predecessors, (460), 134 states have call successors, (134), 53 states have call predecessors, (134), 52 states have return successors, (127), 104 states have call predecessors, (127), 127 states have call successors, (127) [2023-02-15 12:08:05,351 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 549 states to 549 states and 721 transitions. [2023-02-15 12:08:05,351 INFO L78 Accepts]: Start accepts. Automaton has 549 states and 721 transitions. Word has length 96 [2023-02-15 12:08:05,351 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:08:05,351 INFO L495 AbstractCegarLoop]: Abstraction has 549 states and 721 transitions. [2023-02-15 12:08:05,352 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.071428571428571) internal successors, (57), 14 states have internal predecessors, (57), 9 states have call successors, (29), 6 states have call predecessors, (29), 6 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) [2023-02-15 12:08:05,352 INFO L276 IsEmpty]: Start isEmpty. Operand 549 states and 721 transitions. [2023-02-15 12:08:05,352 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2023-02-15 12:08:05,352 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:08:05,353 INFO L195 NwaCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:08:05,367 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-02-15 12:08:05,558 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,SelfDestructingSolverStorable12 [2023-02-15 12:08:05,558 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:08:05,558 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:08:05,558 INFO L85 PathProgramCache]: Analyzing trace with hash -218084043, now seen corresponding path program 2 times [2023-02-15 12:08:05,559 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:08:05,559 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [593395131] [2023-02-15 12:08:05,559 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:08:05,560 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:08:05,569 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:08:05,569 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1260208849] [2023-02-15 12:08:05,569 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-15 12:08:05,569 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:08:05,569 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:08:05,570 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:08:05,572 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-02-15 12:08:05,617 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-15 12:08:05,617 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:08:05,618 INFO L263 TraceCheckSpWp]: Trace formula consists of 262 conjuncts, 48 conjunts are in the unsatisfiable core [2023-02-15 12:08:05,620 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:08:05,909 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 32 proven. 74 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2023-02-15 12:08:05,910 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:08:11,909 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 32 proven. 74 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2023-02-15 12:08:11,910 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:08:11,910 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [593395131] [2023-02-15 12:08:11,910 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:08:11,910 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1260208849] [2023-02-15 12:08:11,910 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1260208849] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:08:11,910 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:08:11,910 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 21 [2023-02-15 12:08:11,910 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1926584569] [2023-02-15 12:08:11,910 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:08:11,910 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-02-15 12:08:11,910 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:08:11,911 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-02-15 12:08:11,911 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=334, Unknown=0, NotChecked=0, Total=420 [2023-02-15 12:08:11,911 INFO L87 Difference]: Start difference. First operand 549 states and 721 transitions. Second operand has 21 states, 19 states have (on average 2.9473684210526314) internal successors, (56), 20 states have internal predecessors, (56), 12 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 10 states have call predecessors, (30), 10 states have call successors, (30) [2023-02-15 12:08:18,289 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.15s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 12:08:23,122 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 12:08:27,262 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:08:27,262 INFO L93 Difference]: Finished difference Result 672 states and 874 transitions. [2023-02-15 12:08:27,263 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2023-02-15 12:08:27,263 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.9473684210526314) internal successors, (56), 20 states have internal predecessors, (56), 12 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 10 states have call predecessors, (30), 10 states have call successors, (30) Word has length 101 [2023-02-15 12:08:27,263 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:08:27,265 INFO L225 Difference]: With dead ends: 672 [2023-02-15 12:08:27,265 INFO L226 Difference]: Without dead ends: 511 [2023-02-15 12:08:27,266 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 178 SyntacticMatches, 3 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 100 ImplicationChecksByTransitivity, 10.2s TimeCoverageRelationStatistics Valid=227, Invalid=765, Unknown=0, NotChecked=0, Total=992 [2023-02-15 12:08:27,267 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 69 mSDsluCounter, 196 mSDsCounter, 0 mSdLazyCounter, 830 mSolverCounterSat, 100 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 72 SdHoareTripleChecker+Valid, 237 SdHoareTripleChecker+Invalid, 931 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 100 IncrementalHoareTripleChecker+Valid, 830 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.2s IncrementalHoareTripleChecker+Time [2023-02-15 12:08:27,267 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [72 Valid, 237 Invalid, 931 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [100 Valid, 830 Invalid, 1 Unknown, 0 Unchecked, 7.2s Time] [2023-02-15 12:08:27,268 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 511 states. [2023-02-15 12:08:27,391 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 511 to 488. [2023-02-15 12:08:27,392 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 488 states, 322 states have (on average 1.2111801242236024) internal successors, (390), 347 states have internal predecessors, (390), 112 states have call successors, (112), 53 states have call predecessors, (112), 53 states have return successors, (107), 87 states have call predecessors, (107), 107 states have call successors, (107) [2023-02-15 12:08:27,394 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 488 states to 488 states and 609 transitions. [2023-02-15 12:08:27,394 INFO L78 Accepts]: Start accepts. Automaton has 488 states and 609 transitions. Word has length 101 [2023-02-15 12:08:27,394 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:08:27,394 INFO L495 AbstractCegarLoop]: Abstraction has 488 states and 609 transitions. [2023-02-15 12:08:27,394 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.9473684210526314) internal successors, (56), 20 states have internal predecessors, (56), 12 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 10 states have call predecessors, (30), 10 states have call successors, (30) [2023-02-15 12:08:27,394 INFO L276 IsEmpty]: Start isEmpty. Operand 488 states and 609 transitions. [2023-02-15 12:08:27,395 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2023-02-15 12:08:27,395 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:08:27,395 INFO L195 NwaCegarLoop]: trace histogram [16, 15, 15, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:08:27,404 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-02-15 12:08:27,596 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,SelfDestructingSolverStorable13 [2023-02-15 12:08:27,596 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:08:27,596 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:08:27,596 INFO L85 PathProgramCache]: Analyzing trace with hash -1246855822, now seen corresponding path program 1 times [2023-02-15 12:08:27,596 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:08:27,596 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1320659103] [2023-02-15 12:08:27,596 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:08:27,596 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:08:27,601 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:08:27,606 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1918116964] [2023-02-15 12:08:27,606 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:08:27,606 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:08:27,606 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:08:27,621 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:08:27,648 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-02-15 12:08:27,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:08:27,676 INFO L263 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 15 conjunts are in the unsatisfiable core [2023-02-15 12:08:27,678 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:08:27,778 INFO L134 CoverageAnalysis]: Checked inductivity of 492 backedges. 30 proven. 414 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-02-15 12:08:27,779 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:08:27,908 INFO L134 CoverageAnalysis]: Checked inductivity of 492 backedges. 30 proven. 42 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2023-02-15 12:08:27,908 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:08:27,908 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1320659103] [2023-02-15 12:08:27,908 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:08:27,909 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1918116964] [2023-02-15 12:08:27,909 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1918116964] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:08:27,909 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:08:27,909 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10] total 18 [2023-02-15 12:08:27,910 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [833814809] [2023-02-15 12:08:27,910 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:08:27,910 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-02-15 12:08:27,910 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:08:27,911 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-02-15 12:08:27,911 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=125, Invalid=181, Unknown=0, NotChecked=0, Total=306 [2023-02-15 12:08:27,911 INFO L87 Difference]: Start difference. First operand 488 states and 609 transitions. Second operand has 18 states, 18 states have (on average 4.111111111111111) internal successors, (74), 18 states have internal predecessors, (74), 13 states have call successors, (31), 8 states have call predecessors, (31), 7 states have return successors, (30), 12 states have call predecessors, (30), 12 states have call successors, (30) [2023-02-15 12:08:28,346 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:08:28,346 INFO L93 Difference]: Finished difference Result 915 states and 1190 transitions. [2023-02-15 12:08:28,346 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2023-02-15 12:08:28,346 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 4.111111111111111) internal successors, (74), 18 states have internal predecessors, (74), 13 states have call successors, (31), 8 states have call predecessors, (31), 7 states have return successors, (30), 12 states have call predecessors, (30), 12 states have call successors, (30) Word has length 104 [2023-02-15 12:08:28,347 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:08:28,349 INFO L225 Difference]: With dead ends: 915 [2023-02-15 12:08:28,349 INFO L226 Difference]: Without dead ends: 880 [2023-02-15 12:08:28,350 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 216 GetRequests, 190 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=259, Invalid=497, Unknown=0, NotChecked=0, Total=756 [2023-02-15 12:08:28,350 INFO L413 NwaCegarLoop]: 94 mSDtfsCounter, 219 mSDsluCounter, 288 mSDsCounter, 0 mSdLazyCounter, 270 mSolverCounterSat, 93 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 219 SdHoareTripleChecker+Valid, 382 SdHoareTripleChecker+Invalid, 363 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 93 IncrementalHoareTripleChecker+Valid, 270 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-02-15 12:08:28,350 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [219 Valid, 382 Invalid, 363 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [93 Valid, 270 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-02-15 12:08:28,351 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 880 states. [2023-02-15 12:08:28,528 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 880 to 867. [2023-02-15 12:08:28,529 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 867 states, 579 states have (on average 1.1468048359240068) internal successors, (664), 619 states have internal predecessors, (664), 206 states have call successors, (206), 81 states have call predecessors, (206), 81 states have return successors, (198), 166 states have call predecessors, (198), 198 states have call successors, (198) [2023-02-15 12:08:28,531 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 867 states to 867 states and 1068 transitions. [2023-02-15 12:08:28,532 INFO L78 Accepts]: Start accepts. Automaton has 867 states and 1068 transitions. Word has length 104 [2023-02-15 12:08:28,532 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:08:28,532 INFO L495 AbstractCegarLoop]: Abstraction has 867 states and 1068 transitions. [2023-02-15 12:08:28,532 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 4.111111111111111) internal successors, (74), 18 states have internal predecessors, (74), 13 states have call successors, (31), 8 states have call predecessors, (31), 7 states have return successors, (30), 12 states have call predecessors, (30), 12 states have call successors, (30) [2023-02-15 12:08:28,532 INFO L276 IsEmpty]: Start isEmpty. Operand 867 states and 1068 transitions. [2023-02-15 12:08:28,535 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2023-02-15 12:08:28,535 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:08:28,536 INFO L195 NwaCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1] [2023-02-15 12:08:28,542 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-02-15 12:08:28,749 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,SelfDestructingSolverStorable14 [2023-02-15 12:08:28,749 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:08:28,749 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:08:28,749 INFO L85 PathProgramCache]: Analyzing trace with hash -405037921, now seen corresponding path program 3 times [2023-02-15 12:08:28,749 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:08:28,749 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [723949335] [2023-02-15 12:08:28,749 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:08:28,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:08:28,755 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:08:28,756 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1176792292] [2023-02-15 12:08:28,756 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-15 12:08:28,756 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:08:28,756 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:08:28,757 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:08:28,759 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-02-15 12:08:28,823 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-02-15 12:08:28,824 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:08:28,825 INFO L263 TraceCheckSpWp]: Trace formula consists of 210 conjuncts, 34 conjunts are in the unsatisfiable core [2023-02-15 12:08:28,827 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:08:29,089 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 159 proven. 47 refuted. 0 times theorem prover too weak. 505 trivial. 0 not checked. [2023-02-15 12:08:29,089 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:08:46,866 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:08:46,866 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [723949335] [2023-02-15 12:08:46,866 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:08:46,866 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1176792292] [2023-02-15 12:08:46,866 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1176792292] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-15 12:08:46,866 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-15 12:08:46,866 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2023-02-15 12:08:46,866 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [561862264] [2023-02-15 12:08:46,866 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-15 12:08:46,866 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-02-15 12:08:46,866 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:08:46,867 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-02-15 12:08:46,867 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=170, Unknown=0, NotChecked=0, Total=210 [2023-02-15 12:08:46,867 INFO L87 Difference]: Start difference. First operand 867 states and 1068 transitions. Second operand has 10 states, 10 states have (on average 2.6) internal successors, (26), 9 states have internal predecessors, (26), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 4 states have call predecessors, (11), 3 states have call successors, (11) [2023-02-15 12:08:47,184 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:08:47,185 INFO L93 Difference]: Finished difference Result 898 states and 1098 transitions. [2023-02-15 12:08:47,185 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-02-15 12:08:47,185 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.6) internal successors, (26), 9 states have internal predecessors, (26), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 4 states have call predecessors, (11), 3 states have call successors, (11) Word has length 122 [2023-02-15 12:08:47,185 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:08:47,188 INFO L225 Difference]: With dead ends: 898 [2023-02-15 12:08:47,188 INFO L226 Difference]: Without dead ends: 884 [2023-02-15 12:08:47,188 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 116 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=63, Invalid=243, Unknown=0, NotChecked=0, Total=306 [2023-02-15 12:08:47,189 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 39 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 153 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 153 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 12:08:47,189 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 73 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 153 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 12:08:47,191 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 884 states. [2023-02-15 12:08:47,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 884 to 868. [2023-02-15 12:08:47,376 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 868 states, 584 states have (on average 1.1352739726027397) internal successors, (663), 618 states have internal predecessors, (663), 201 states have call successors, (201), 83 states have call predecessors, (201), 82 states have return successors, (198), 166 states have call predecessors, (198), 198 states have call successors, (198) [2023-02-15 12:08:47,378 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 868 states to 868 states and 1062 transitions. [2023-02-15 12:08:47,379 INFO L78 Accepts]: Start accepts. Automaton has 868 states and 1062 transitions. Word has length 122 [2023-02-15 12:08:47,379 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:08:47,379 INFO L495 AbstractCegarLoop]: Abstraction has 868 states and 1062 transitions. [2023-02-15 12:08:47,379 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.6) internal successors, (26), 9 states have internal predecessors, (26), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 4 states have call predecessors, (11), 3 states have call successors, (11) [2023-02-15 12:08:47,379 INFO L276 IsEmpty]: Start isEmpty. Operand 868 states and 1062 transitions. [2023-02-15 12:08:47,382 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 134 [2023-02-15 12:08:47,382 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:08:47,382 INFO L195 NwaCegarLoop]: trace histogram [21, 20, 20, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:08:47,387 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-15 12:08:47,587 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:08:47,588 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:08:47,588 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:08:47,588 INFO L85 PathProgramCache]: Analyzing trace with hash 1989463840, now seen corresponding path program 3 times [2023-02-15 12:08:47,588 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:08:47,588 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1888352571] [2023-02-15 12:08:47,588 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:08:47,588 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:08:47,599 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:08:47,599 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1369766731] [2023-02-15 12:08:47,599 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-15 12:08:47,599 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:08:47,599 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:08:47,601 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:08:47,602 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2023-02-15 12:08:47,654 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-02-15 12:08:47,654 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:08:47,656 INFO L263 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 27 conjunts are in the unsatisfiable core [2023-02-15 12:08:47,657 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:08:47,787 INFO L134 CoverageAnalysis]: Checked inductivity of 869 backedges. 163 proven. 56 refuted. 0 times theorem prover too weak. 650 trivial. 0 not checked. [2023-02-15 12:08:47,788 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:08:47,913 INFO L134 CoverageAnalysis]: Checked inductivity of 869 backedges. 152 proven. 2 refuted. 0 times theorem prover too weak. 715 trivial. 0 not checked. [2023-02-15 12:08:47,913 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:08:47,913 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1888352571] [2023-02-15 12:08:47,913 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:08:47,913 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1369766731] [2023-02-15 12:08:47,913 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1369766731] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:08:47,913 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:08:47,914 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 16 [2023-02-15 12:08:47,914 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1353297460] [2023-02-15 12:08:47,914 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:08:47,914 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-02-15 12:08:47,914 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:08:47,915 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-02-15 12:08:47,915 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2023-02-15 12:08:47,915 INFO L87 Difference]: Start difference. First operand 868 states and 1062 transitions. Second operand has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 7 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) [2023-02-15 12:08:48,264 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:08:48,264 INFO L93 Difference]: Finished difference Result 875 states and 1068 transitions. [2023-02-15 12:08:48,277 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-02-15 12:08:48,277 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 7 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) Word has length 133 [2023-02-15 12:08:48,277 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:08:48,280 INFO L225 Difference]: With dead ends: 875 [2023-02-15 12:08:48,280 INFO L226 Difference]: Without dead ends: 865 [2023-02-15 12:08:48,280 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 273 GetRequests, 252 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 61 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=108, Invalid=398, Unknown=0, NotChecked=0, Total=506 [2023-02-15 12:08:48,281 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 68 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 232 mSolverCounterSat, 61 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 293 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 61 IncrementalHoareTripleChecker+Valid, 232 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 12:08:48,281 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [68 Valid, 98 Invalid, 293 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [61 Valid, 232 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 12:08:48,282 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 865 states. [2023-02-15 12:08:48,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 865 to 557. [2023-02-15 12:08:48,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 557 states, 374 states have (on average 1.106951871657754) internal successors, (414), 394 states have internal predecessors, (414), 115 states have call successors, (115), 67 states have call predecessors, (115), 67 states have return successors, (114), 95 states have call predecessors, (114), 114 states have call successors, (114) [2023-02-15 12:08:48,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 557 states to 557 states and 643 transitions. [2023-02-15 12:08:48,443 INFO L78 Accepts]: Start accepts. Automaton has 557 states and 643 transitions. Word has length 133 [2023-02-15 12:08:48,444 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:08:48,444 INFO L495 AbstractCegarLoop]: Abstraction has 557 states and 643 transitions. [2023-02-15 12:08:48,444 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 7 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) [2023-02-15 12:08:48,444 INFO L276 IsEmpty]: Start isEmpty. Operand 557 states and 643 transitions. [2023-02-15 12:08:48,446 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 217 [2023-02-15 12:08:48,446 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:08:48,446 INFO L195 NwaCegarLoop]: trace histogram [32, 31, 31, 12, 11, 11, 11, 11, 11, 11, 10, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:08:48,461 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2023-02-15 12:08:48,652 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,SelfDestructingSolverStorable16 [2023-02-15 12:08:48,652 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:08:48,652 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:08:48,652 INFO L85 PathProgramCache]: Analyzing trace with hash 694795218, now seen corresponding path program 2 times [2023-02-15 12:08:48,653 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:08:48,653 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1209666627] [2023-02-15 12:08:48,653 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:08:48,653 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:08:48,661 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:08:48,661 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [900488484] [2023-02-15 12:08:48,661 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-15 12:08:48,662 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:08:48,662 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:08:48,670 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:08:48,671 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2023-02-15 12:08:48,755 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-15 12:08:48,755 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:08:48,757 INFO L263 TraceCheckSpWp]: Trace formula consists of 535 conjuncts, 31 conjunts are in the unsatisfiable core [2023-02-15 12:08:48,760 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:08:49,064 INFO L134 CoverageAnalysis]: Checked inductivity of 2292 backedges. 62 proven. 2150 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2023-02-15 12:08:49,064 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:08:49,469 INFO L134 CoverageAnalysis]: Checked inductivity of 2292 backedges. 62 proven. 370 refuted. 0 times theorem prover too weak. 1860 trivial. 0 not checked. [2023-02-15 12:08:49,469 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:08:49,469 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1209666627] [2023-02-15 12:08:49,469 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:08:49,469 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [900488484] [2023-02-15 12:08:49,469 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [900488484] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:08:49,469 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:08:49,469 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 18] total 34 [2023-02-15 12:08:49,469 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [746713951] [2023-02-15 12:08:49,469 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:08:49,470 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2023-02-15 12:08:49,470 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:08:49,471 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2023-02-15 12:08:49,471 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=501, Invalid=621, Unknown=0, NotChecked=0, Total=1122 [2023-02-15 12:08:49,471 INFO L87 Difference]: Start difference. First operand 557 states and 643 transitions. Second operand has 34 states, 34 states have (on average 4.764705882352941) internal successors, (162), 34 states have internal predecessors, (162), 29 states have call successors, (63), 16 states have call predecessors, (63), 15 states have return successors, (62), 28 states have call predecessors, (62), 28 states have call successors, (62) [2023-02-15 12:08:50,769 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:08:50,770 INFO L93 Difference]: Finished difference Result 1291 states and 1585 transitions. [2023-02-15 12:08:50,793 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2023-02-15 12:08:50,793 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 34 states have (on average 4.764705882352941) internal successors, (162), 34 states have internal predecessors, (162), 29 states have call successors, (63), 16 states have call predecessors, (63), 15 states have return successors, (62), 28 states have call predecessors, (62), 28 states have call successors, (62) Word has length 216 [2023-02-15 12:08:50,796 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:08:50,800 INFO L225 Difference]: With dead ends: 1291 [2023-02-15 12:08:50,800 INFO L226 Difference]: Without dead ends: 1278 [2023-02-15 12:08:50,801 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 456 GetRequests, 398 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 459 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=1267, Invalid=2273, Unknown=0, NotChecked=0, Total=3540 [2023-02-15 12:08:50,802 INFO L413 NwaCegarLoop]: 167 mSDtfsCounter, 641 mSDsluCounter, 675 mSDsCounter, 0 mSdLazyCounter, 649 mSolverCounterSat, 440 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 641 SdHoareTripleChecker+Valid, 842 SdHoareTripleChecker+Invalid, 1089 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 440 IncrementalHoareTripleChecker+Valid, 649 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-02-15 12:08:50,802 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [641 Valid, 842 Invalid, 1089 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [440 Valid, 649 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-02-15 12:08:50,804 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1278 states. [2023-02-15 12:08:51,222 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1278 to 1277. [2023-02-15 12:08:51,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1277 states, 854 states have (on average 1.1217798594847774) internal successors, (958), 906 states have internal predecessors, (958), 275 states have call successors, (275), 147 states have call predecessors, (275), 147 states have return successors, (274), 223 states have call predecessors, (274), 274 states have call successors, (274) [2023-02-15 12:08:51,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1277 states to 1277 states and 1507 transitions. [2023-02-15 12:08:51,227 INFO L78 Accepts]: Start accepts. Automaton has 1277 states and 1507 transitions. Word has length 216 [2023-02-15 12:08:51,229 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:08:51,229 INFO L495 AbstractCegarLoop]: Abstraction has 1277 states and 1507 transitions. [2023-02-15 12:08:51,229 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 34 states have (on average 4.764705882352941) internal successors, (162), 34 states have internal predecessors, (162), 29 states have call successors, (63), 16 states have call predecessors, (63), 15 states have return successors, (62), 28 states have call predecessors, (62), 28 states have call successors, (62) [2023-02-15 12:08:51,229 INFO L276 IsEmpty]: Start isEmpty. Operand 1277 states and 1507 transitions. [2023-02-15 12:08:51,240 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 441 [2023-02-15 12:08:51,240 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:08:51,240 INFO L195 NwaCegarLoop]: trace histogram [64, 63, 63, 28, 27, 27, 27, 27, 27, 27, 26, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:08:51,257 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2023-02-15 12:08:51,447 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,SelfDestructingSolverStorable17 [2023-02-15 12:08:51,447 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:08:51,447 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:08:51,447 INFO L85 PathProgramCache]: Analyzing trace with hash -743933806, now seen corresponding path program 3 times [2023-02-15 12:08:51,447 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:08:51,448 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [437324887] [2023-02-15 12:08:51,448 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:08:51,448 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:08:51,461 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:08:51,461 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2021487649] [2023-02-15 12:08:51,461 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-15 12:08:51,461 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:08:51,462 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:08:51,462 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:08:51,464 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2023-02-15 12:08:52,794 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 27 check-sat command(s) [2023-02-15 12:08:52,795 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:08:52,800 INFO L263 TraceCheckSpWp]: Trace formula consists of 658 conjuncts, 8 conjunts are in the unsatisfiable core [2023-02-15 12:08:52,805 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:08:52,890 INFO L134 CoverageAnalysis]: Checked inductivity of 10116 backedges. 2486 proven. 0 refuted. 0 times theorem prover too weak. 7630 trivial. 0 not checked. [2023-02-15 12:08:52,890 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 12:08:52,890 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:08:52,890 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [437324887] [2023-02-15 12:08:52,890 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:08:52,890 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2021487649] [2023-02-15 12:08:52,891 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2021487649] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 12:08:52,891 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 12:08:52,891 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-02-15 12:08:52,891 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1052302345] [2023-02-15 12:08:52,891 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 12:08:52,892 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-02-15 12:08:52,892 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:08:52,892 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-02-15 12:08:52,892 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2023-02-15 12:08:52,892 INFO L87 Difference]: Start difference. First operand 1277 states and 1507 transitions. Second operand has 6 states, 6 states have (on average 4.666666666666667) internal successors, (28), 6 states have internal predecessors, (28), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2023-02-15 12:08:53,485 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:08:53,485 INFO L93 Difference]: Finished difference Result 2101 states and 2551 transitions. [2023-02-15 12:08:53,486 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-15 12:08:53,486 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.666666666666667) internal successors, (28), 6 states have internal predecessors, (28), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) Word has length 440 [2023-02-15 12:08:53,486 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:08:53,490 INFO L225 Difference]: With dead ends: 2101 [2023-02-15 12:08:53,491 INFO L226 Difference]: Without dead ends: 1482 [2023-02-15 12:08:53,492 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 440 GetRequests, 435 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2023-02-15 12:08:53,492 INFO L413 NwaCegarLoop]: 56 mSDtfsCounter, 17 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 87 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 12:08:53,493 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 107 Invalid, 87 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 12:08:53,494 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1482 states. [2023-02-15 12:08:53,831 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1482 to 1143. [2023-02-15 12:08:53,833 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1143 states, 780 states have (on average 1.0974358974358975) internal successors, (856), 806 states have internal predecessors, (856), 219 states have call successors, (219), 143 states have call predecessors, (219), 143 states have return successors, (218), 193 states have call predecessors, (218), 218 states have call successors, (218) [2023-02-15 12:08:53,835 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1143 states to 1143 states and 1293 transitions. [2023-02-15 12:08:53,836 INFO L78 Accepts]: Start accepts. Automaton has 1143 states and 1293 transitions. Word has length 440 [2023-02-15 12:08:53,836 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:08:53,836 INFO L495 AbstractCegarLoop]: Abstraction has 1143 states and 1293 transitions. [2023-02-15 12:08:53,836 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.666666666666667) internal successors, (28), 6 states have internal predecessors, (28), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2023-02-15 12:08:53,836 INFO L276 IsEmpty]: Start isEmpty. Operand 1143 states and 1293 transitions. [2023-02-15 12:08:53,843 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 445 [2023-02-15 12:08:53,843 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:08:53,844 INFO L195 NwaCegarLoop]: trace histogram [65, 64, 64, 27, 26, 26, 26, 26, 26, 26, 26, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:08:53,863 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2023-02-15 12:08:54,051 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:08:54,052 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:08:54,052 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:08:54,052 INFO L85 PathProgramCache]: Analyzing trace with hash 1525085741, now seen corresponding path program 1 times [2023-02-15 12:08:54,052 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:08:54,052 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1574632811] [2023-02-15 12:08:54,052 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:08:54,052 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:08:54,084 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:08:54,084 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1523987076] [2023-02-15 12:08:54,084 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:08:54,084 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:08:54,084 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:08:54,092 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:08:54,093 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2023-02-15 12:08:54,251 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 12:08:54,255 INFO L263 TraceCheckSpWp]: Trace formula consists of 1071 conjuncts, 63 conjunts are in the unsatisfiable core [2023-02-15 12:08:54,261 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:08:54,945 INFO L134 CoverageAnalysis]: Checked inductivity of 10230 backedges. 128 proven. 9950 refuted. 0 times theorem prover too weak. 152 trivial. 0 not checked. [2023-02-15 12:08:54,945 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:08:55,994 INFO L134 CoverageAnalysis]: Checked inductivity of 10230 backedges. 128 proven. 2038 refuted. 0 times theorem prover too weak. 8064 trivial. 0 not checked. [2023-02-15 12:08:55,994 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:08:55,994 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1574632811] [2023-02-15 12:08:55,994 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:08:55,994 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1523987076] [2023-02-15 12:08:55,994 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1523987076] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:08:55,994 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:08:55,994 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 34] total 54 [2023-02-15 12:08:55,994 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [459811949] [2023-02-15 12:08:55,994 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:08:55,995 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 54 states [2023-02-15 12:08:55,995 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:08:55,996 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2023-02-15 12:08:55,997 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1331, Invalid=1531, Unknown=0, NotChecked=0, Total=2862 [2023-02-15 12:08:55,997 INFO L87 Difference]: Start difference. First operand 1143 states and 1293 transitions. Second operand has 54 states, 54 states have (on average 5.703703703703703) internal successors, (308), 54 states have internal predecessors, (308), 50 states have call successors, (129), 32 states have call predecessors, (129), 31 states have return successors, (128), 49 states have call predecessors, (128), 49 states have call successors, (128) [2023-02-15 12:08:58,756 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:08:58,756 INFO L93 Difference]: Finished difference Result 1977 states and 2307 transitions. [2023-02-15 12:08:58,757 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 98 states. [2023-02-15 12:08:58,757 INFO L78 Accepts]: Start accepts. Automaton has has 54 states, 54 states have (on average 5.703703703703703) internal successors, (308), 54 states have internal predecessors, (308), 50 states have call successors, (129), 32 states have call predecessors, (129), 31 states have return successors, (128), 49 states have call predecessors, (128), 49 states have call successors, (128) Word has length 444 [2023-02-15 12:08:58,757 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:08:58,762 INFO L225 Difference]: With dead ends: 1977 [2023-02-15 12:08:58,762 INFO L226 Difference]: Without dead ends: 1964 [2023-02-15 12:08:58,765 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 931 GetRequests, 822 SyntacticMatches, 12 SemanticMatches, 97 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1516 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=3518, Invalid=6184, Unknown=0, NotChecked=0, Total=9702 [2023-02-15 12:08:58,766 INFO L413 NwaCegarLoop]: 265 mSDtfsCounter, 1082 mSDsluCounter, 1038 mSDsCounter, 0 mSdLazyCounter, 1383 mSolverCounterSat, 765 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1082 SdHoareTripleChecker+Valid, 1303 SdHoareTripleChecker+Invalid, 2148 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 765 IncrementalHoareTripleChecker+Valid, 1383 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2023-02-15 12:08:58,766 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1082 Valid, 1303 Invalid, 2148 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [765 Valid, 1383 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2023-02-15 12:08:58,771 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1964 states. [2023-02-15 12:08:59,356 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1964 to 1963. [2023-02-15 12:08:59,358 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1963 states, 1340 states have (on average 1.1014925373134328) internal successors, (1476), 1386 states have internal predecessors, (1476), 379 states have call successors, (379), 243 states have call predecessors, (379), 243 states have return successors, (378), 333 states have call predecessors, (378), 378 states have call successors, (378) [2023-02-15 12:08:59,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1963 states to 1963 states and 2233 transitions. [2023-02-15 12:08:59,364 INFO L78 Accepts]: Start accepts. Automaton has 1963 states and 2233 transitions. Word has length 444 [2023-02-15 12:08:59,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:08:59,365 INFO L495 AbstractCegarLoop]: Abstraction has 1963 states and 2233 transitions. [2023-02-15 12:08:59,365 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 54 states, 54 states have (on average 5.703703703703703) internal successors, (308), 54 states have internal predecessors, (308), 50 states have call successors, (129), 32 states have call predecessors, (129), 31 states have return successors, (128), 49 states have call predecessors, (128), 49 states have call successors, (128) [2023-02-15 12:08:59,365 INFO L276 IsEmpty]: Start isEmpty. Operand 1963 states and 2233 transitions. [2023-02-15 12:08:59,372 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 725 [2023-02-15 12:08:59,372 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:08:59,372 INFO L195 NwaCegarLoop]: trace histogram [105, 104, 104, 47, 46, 46, 46, 46, 46, 46, 46, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:08:59,378 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2023-02-15 12:08:59,578 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:08:59,578 INFO L420 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:08:59,578 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:08:59,579 INFO L85 PathProgramCache]: Analyzing trace with hash -554493667, now seen corresponding path program 2 times [2023-02-15 12:08:59,579 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:08:59,579 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1709363004] [2023-02-15 12:08:59,579 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:08:59,579 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:08:59,596 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:08:59,597 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [375937195] [2023-02-15 12:08:59,597 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-15 12:08:59,597 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:08:59,597 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:08:59,598 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:08:59,602 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2023-02-15 12:08:59,909 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-15 12:08:59,909 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:08:59,917 INFO L263 TraceCheckSpWp]: Trace formula consists of 1731 conjuncts, 32 conjunts are in the unsatisfiable core [2023-02-15 12:08:59,924 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:09:00,171 INFO L134 CoverageAnalysis]: Checked inductivity of 27970 backedges. 7737 proven. 69 refuted. 0 times theorem prover too weak. 20164 trivial. 0 not checked. [2023-02-15 12:09:00,171 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:09:04,152 INFO L134 CoverageAnalysis]: Checked inductivity of 27970 backedges. 1185 proven. 69 refuted. 0 times theorem prover too weak. 26716 trivial. 0 not checked. [2023-02-15 12:09:04,152 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:09:04,152 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1709363004] [2023-02-15 12:09:04,152 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:09:04,152 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [375937195] [2023-02-15 12:09:04,152 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [375937195] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:09:04,152 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:09:04,152 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 23 [2023-02-15 12:09:04,152 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1619864010] [2023-02-15 12:09:04,152 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:09:04,153 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2023-02-15 12:09:04,153 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:09:04,154 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2023-02-15 12:09:04,154 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=423, Unknown=0, NotChecked=0, Total=506 [2023-02-15 12:09:04,154 INFO L87 Difference]: Start difference. First operand 1963 states and 2233 transitions. Second operand has 23 states, 23 states have (on average 2.9130434782608696) internal successors, (67), 23 states have internal predecessors, (67), 16 states have call successors, (43), 2 states have call predecessors, (43), 2 states have return successors, (42), 16 states have call predecessors, (42), 16 states have call successors, (42) [2023-02-15 12:09:05,496 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:09:05,496 INFO L93 Difference]: Finished difference Result 2990 states and 3477 transitions. [2023-02-15 12:09:05,497 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-02-15 12:09:05,497 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.9130434782608696) internal successors, (67), 23 states have internal predecessors, (67), 16 states have call successors, (43), 2 states have call predecessors, (43), 2 states have return successors, (42), 16 states have call predecessors, (42), 16 states have call successors, (42) Word has length 724 [2023-02-15 12:09:05,497 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:09:05,502 INFO L225 Difference]: With dead ends: 2990 [2023-02-15 12:09:05,502 INFO L226 Difference]: Without dead ends: 2226 [2023-02-15 12:09:05,504 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1452 GetRequests, 1425 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 124 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=136, Invalid=676, Unknown=0, NotChecked=0, Total=812 [2023-02-15 12:09:05,504 INFO L413 NwaCegarLoop]: 79 mSDtfsCounter, 22 mSDsluCounter, 464 mSDsCounter, 0 mSdLazyCounter, 689 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 543 SdHoareTripleChecker+Invalid, 729 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 689 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-02-15 12:09:05,504 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 543 Invalid, 729 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 689 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-02-15 12:09:05,505 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2226 states. [2023-02-15 12:09:06,167 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2226 to 1940. [2023-02-15 12:09:06,169 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1940 states, 1324 states have (on average 1.1012084592145015) internal successors, (1458), 1369 states have internal predecessors, (1458), 374 states have call successors, (374), 241 states have call predecessors, (374), 241 states have return successors, (373), 329 states have call predecessors, (373), 373 states have call successors, (373) [2023-02-15 12:09:06,175 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1940 states to 1940 states and 2205 transitions. [2023-02-15 12:09:06,175 INFO L78 Accepts]: Start accepts. Automaton has 1940 states and 2205 transitions. Word has length 724 [2023-02-15 12:09:06,176 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:09:06,176 INFO L495 AbstractCegarLoop]: Abstraction has 1940 states and 2205 transitions. [2023-02-15 12:09:06,176 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.9130434782608696) internal successors, (67), 23 states have internal predecessors, (67), 16 states have call successors, (43), 2 states have call predecessors, (43), 2 states have return successors, (42), 16 states have call predecessors, (42), 16 states have call successors, (42) [2023-02-15 12:09:06,176 INFO L276 IsEmpty]: Start isEmpty. Operand 1940 states and 2205 transitions. [2023-02-15 12:09:06,182 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 729 [2023-02-15 12:09:06,182 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:09:06,183 INFO L195 NwaCegarLoop]: trace histogram [106, 105, 105, 46, 45, 45, 45, 45, 45, 45, 45, 5, 5, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:09:06,190 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2023-02-15 12:09:06,390 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:09:06,391 INFO L420 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:09:06,392 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:09:06,392 INFO L85 PathProgramCache]: Analyzing trace with hash 1342293370, now seen corresponding path program 3 times [2023-02-15 12:09:06,392 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:09:06,392 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1108726738] [2023-02-15 12:09:06,392 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:09:06,392 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:09:06,409 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:09:06,409 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [755390071] [2023-02-15 12:09:06,409 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-15 12:09:06,409 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:09:06,409 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:09:06,426 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:09:06,427 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2023-02-15 12:09:35,404 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 69 check-sat command(s) [2023-02-15 12:09:35,404 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 12:09:35,428 INFO L263 TraceCheckSpWp]: Trace formula consists of 1726 conjuncts, 52 conjunts are in the unsatisfiable core [2023-02-15 12:09:35,451 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 12:09:35,907 INFO L134 CoverageAnalysis]: Checked inductivity of 28140 backedges. 9281 proven. 131 refuted. 0 times theorem prover too weak. 18728 trivial. 0 not checked. [2023-02-15 12:09:35,907 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 12:09:59,817 INFO L134 CoverageAnalysis]: Checked inductivity of 28140 backedges. 1441 proven. 371 refuted. 0 times theorem prover too weak. 26328 trivial. 0 not checked. [2023-02-15 12:09:59,818 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 12:09:59,818 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1108726738] [2023-02-15 12:09:59,818 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 12:09:59,818 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [755390071] [2023-02-15 12:09:59,818 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [755390071] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 12:09:59,818 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 12:09:59,818 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 26 [2023-02-15 12:09:59,818 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1420360102] [2023-02-15 12:09:59,818 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 12:09:59,819 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-02-15 12:09:59,819 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 12:09:59,819 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-02-15 12:09:59,820 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=563, Unknown=0, NotChecked=0, Total=650 [2023-02-15 12:09:59,820 INFO L87 Difference]: Start difference. First operand 1940 states and 2205 transitions. Second operand has 26 states, 26 states have (on average 3.269230769230769) internal successors, (85), 24 states have internal predecessors, (85), 20 states have call successors, (53), 2 states have call predecessors, (53), 3 states have return successors, (52), 18 states have call predecessors, (52), 20 states have call successors, (52) [2023-02-15 12:10:03,313 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 12:10:03,935 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 12:10:03,936 INFO L93 Difference]: Finished difference Result 2664 states and 3023 transitions. [2023-02-15 12:10:03,937 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-02-15 12:10:03,937 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 3.269230769230769) internal successors, (85), 24 states have internal predecessors, (85), 20 states have call successors, (53), 2 states have call predecessors, (53), 3 states have return successors, (52), 18 states have call predecessors, (52), 20 states have call successors, (52) Word has length 728 [2023-02-15 12:10:03,937 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 12:10:03,963 INFO L225 Difference]: With dead ends: 2664 [2023-02-15 12:10:03,963 INFO L226 Difference]: Without dead ends: 1917 [2023-02-15 12:10:03,965 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1455 GetRequests, 1429 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 85 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=92, Invalid=610, Unknown=0, NotChecked=0, Total=702 [2023-02-15 12:10:03,966 INFO L413 NwaCegarLoop]: 59 mSDtfsCounter, 22 mSDsluCounter, 297 mSDsCounter, 0 mSdLazyCounter, 996 mSolverCounterSat, 50 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 356 SdHoareTripleChecker+Invalid, 1047 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 996 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.4s IncrementalHoareTripleChecker+Time [2023-02-15 12:10:03,966 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 356 Invalid, 1047 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 996 Invalid, 1 Unknown, 0 Unchecked, 3.4s Time] [2023-02-15 12:10:03,967 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1917 states. [2023-02-15 12:10:04,563 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1917 to 1917. [2023-02-15 12:10:04,566 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1917 states, 1308 states have (on average 1.1009174311926606) internal successors, (1440), 1352 states have internal predecessors, (1440), 369 states have call successors, (369), 239 states have call predecessors, (369), 239 states have return successors, (368), 325 states have call predecessors, (368), 368 states have call successors, (368) [2023-02-15 12:10:04,569 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1917 states to 1917 states and 2177 transitions. [2023-02-15 12:10:04,569 INFO L78 Accepts]: Start accepts. Automaton has 1917 states and 2177 transitions. Word has length 728 [2023-02-15 12:10:04,570 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 12:10:04,570 INFO L495 AbstractCegarLoop]: Abstraction has 1917 states and 2177 transitions. [2023-02-15 12:10:04,570 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 3.269230769230769) internal successors, (85), 24 states have internal predecessors, (85), 20 states have call successors, (53), 2 states have call predecessors, (53), 3 states have return successors, (52), 18 states have call predecessors, (52), 20 states have call successors, (52) [2023-02-15 12:10:04,570 INFO L276 IsEmpty]: Start isEmpty. Operand 1917 states and 2177 transitions. [2023-02-15 12:10:04,578 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 733 [2023-02-15 12:10:04,578 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 12:10:04,578 INFO L195 NwaCegarLoop]: trace histogram [107, 106, 106, 45, 44, 44, 44, 44, 44, 44, 44, 6, 6, 6, 6, 6, 6, 6, 6, 5, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 12:10:04,603 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-15 12:10:04,789 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable21 [2023-02-15 12:10:04,790 INFO L420 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 12:10:04,790 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 12:10:04,790 INFO L85 PathProgramCache]: Analyzing trace with hash -1098331113, now seen corresponding path program 4 times [2023-02-15 12:10:04,790 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 12:10:04,793 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1616978106] [2023-02-15 12:10:04,793 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 12:10:04,793 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 12:10:04,829 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 12:10:04,844 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2115241446] [2023-02-15 12:10:04,845 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-02-15 12:10:04,845 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 12:10:04,845 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 12:10:04,846 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 12:10:04,848 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process