./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/array-tiling/pnr5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version f4b24e32 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/array-tiling/pnr5.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 c6dc18f387244e600c9c46c5a67fb3c0c9875a9a14eb13d3a621343f4a214b0b --- Real Ultimate output --- This is Ultimate 0.2.2-?-f4b24e3 [2022-07-13 10:12:00,712 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-13 10:12:00,720 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-13 10:12:00,754 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-13 10:12:00,755 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-13 10:12:00,756 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-13 10:12:00,757 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-13 10:12:00,759 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-13 10:12:00,761 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-13 10:12:00,762 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-13 10:12:00,763 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-13 10:12:00,764 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-13 10:12:00,764 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-13 10:12:00,765 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-13 10:12:00,766 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-13 10:12:00,767 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-13 10:12:00,768 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-13 10:12:00,769 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-13 10:12:00,771 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-13 10:12:00,772 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-13 10:12:00,774 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-13 10:12:00,775 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-13 10:12:00,776 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-13 10:12:00,777 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-13 10:12:00,778 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-13 10:12:00,781 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-13 10:12:00,781 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-13 10:12:00,782 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-13 10:12:00,783 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-13 10:12:00,783 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-13 10:12:00,784 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-13 10:12:00,784 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-13 10:12:00,785 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-13 10:12:00,786 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-13 10:12:00,787 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-13 10:12:00,788 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-13 10:12:00,790 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-13 10:12:00,791 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-13 10:12:00,792 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-13 10:12:00,792 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-13 10:12:00,793 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-13 10:12:00,795 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-13 10:12:00,797 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2022-07-13 10:12:00,823 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-13 10:12:00,824 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-13 10:12:00,824 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-13 10:12:00,825 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-13 10:12:00,825 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-07-13 10:12:00,826 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-07-13 10:12:00,826 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-13 10:12:00,827 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-13 10:12:00,827 INFO L138 SettingsManager]: * Use SBE=true [2022-07-13 10:12:00,828 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-13 10:12:00,828 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-13 10:12:00,828 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-13 10:12:00,828 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-13 10:12:00,829 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-13 10:12:00,829 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-07-13 10:12:00,829 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-07-13 10:12:00,829 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-07-13 10:12:00,829 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-13 10:12:00,830 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-13 10:12:00,831 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-13 10:12:00,831 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-07-13 10:12:00,831 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-13 10:12:00,832 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-13 10:12:00,832 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-07-13 10:12:00,832 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-13 10:12:00,832 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-13 10:12:00,832 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-07-13 10:12:00,833 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-07-13 10:12:00,833 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-13 10:12:00,833 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-07-13 10:12:00,833 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-07-13 10:12:00,834 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-07-13 10:12:00,834 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-07-13 10:12:00,834 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.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 -> c6dc18f387244e600c9c46c5a67fb3c0c9875a9a14eb13d3a621343f4a214b0b [2022-07-13 10:12:01,096 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-13 10:12:01,120 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-13 10:12:01,122 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-13 10:12:01,123 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-13 10:12:01,124 INFO L275 PluginConnector]: CDTParser initialized [2022-07-13 10:12:01,125 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-tiling/pnr5.c [2022-07-13 10:12:01,188 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/519e82ff4/a7dbde2d5e794959a638832d4792815f/FLAGc92fc9452 [2022-07-13 10:12:01,661 INFO L306 CDTParser]: Found 1 translation units. [2022-07-13 10:12:01,662 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-tiling/pnr5.c [2022-07-13 10:12:01,671 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/519e82ff4/a7dbde2d5e794959a638832d4792815f/FLAGc92fc9452 [2022-07-13 10:12:02,070 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/519e82ff4/a7dbde2d5e794959a638832d4792815f [2022-07-13 10:12:02,072 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-13 10:12:02,073 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-13 10:12:02,075 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-13 10:12:02,075 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-13 10:12:02,078 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-13 10:12:02,079 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.07 10:12:02" (1/1) ... [2022-07-13 10:12:02,080 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@53cd3ee8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 10:12:02, skipping insertion in model container [2022-07-13 10:12:02,080 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.07 10:12:02" (1/1) ... [2022-07-13 10:12:02,086 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-13 10:12:02,100 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-13 10:12:02,252 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-tiling/pnr5.c[395,408] [2022-07-13 10:12:02,299 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-13 10:12:02,311 INFO L203 MainTranslator]: Completed pre-run [2022-07-13 10:12:02,328 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-tiling/pnr5.c[395,408] [2022-07-13 10:12:02,340 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-13 10:12:02,352 INFO L208 MainTranslator]: Completed translation [2022-07-13 10:12:02,353 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 10:12:02 WrapperNode [2022-07-13 10:12:02,353 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-13 10:12:02,354 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-13 10:12:02,354 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-13 10:12:02,354 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-13 10:12:02,360 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 10:12:02" (1/1) ... [2022-07-13 10:12:02,373 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 10:12:02" (1/1) ... [2022-07-13 10:12:02,410 INFO L137 Inliner]: procedures = 17, calls = 33, calls flagged for inlining = 4, calls inlined = 4, statements flattened = 98 [2022-07-13 10:12:02,414 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-13 10:12:02,415 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-13 10:12:02,416 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-13 10:12:02,416 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-13 10:12:02,424 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 10:12:02" (1/1) ... [2022-07-13 10:12:02,424 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 10:12:02" (1/1) ... [2022-07-13 10:12:02,429 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 10:12:02" (1/1) ... [2022-07-13 10:12:02,431 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 10:12:02" (1/1) ... [2022-07-13 10:12:02,445 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 10:12:02" (1/1) ... [2022-07-13 10:12:02,451 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 10:12:02" (1/1) ... [2022-07-13 10:12:02,458 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 10:12:02" (1/1) ... [2022-07-13 10:12:02,465 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-13 10:12:02,468 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-13 10:12:02,468 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-13 10:12:02,469 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-13 10:12:02,470 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 10:12:02" (1/1) ... [2022-07-13 10:12:02,476 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-13 10:12:02,487 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:02,505 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-07-13 10:12:02,525 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-07-13 10:12:02,552 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-13 10:12:02,552 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-13 10:12:02,553 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-07-13 10:12:02,554 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2022-07-13 10:12:02,554 INFO L130 BoogieDeclarations]: Found specification of procedure ReadFromPort [2022-07-13 10:12:02,554 INFO L138 BoogieDeclarations]: Found implementation of procedure ReadFromPort [2022-07-13 10:12:02,557 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-13 10:12:02,557 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-13 10:12:02,557 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-07-13 10:12:02,620 INFO L234 CfgBuilder]: Building ICFG [2022-07-13 10:12:02,621 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-13 10:12:02,904 INFO L275 CfgBuilder]: Performing block encoding [2022-07-13 10:12:02,910 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-13 10:12:02,910 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-07-13 10:12:02,912 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.07 10:12:02 BoogieIcfgContainer [2022-07-13 10:12:02,912 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-13 10:12:02,914 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-07-13 10:12:02,914 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-07-13 10:12:02,930 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-07-13 10:12:02,930 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 13.07 10:12:02" (1/3) ... [2022-07-13 10:12:02,931 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d6d3a46 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 13.07 10:12:02, skipping insertion in model container [2022-07-13 10:12:02,931 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 10:12:02" (2/3) ... [2022-07-13 10:12:02,932 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d6d3a46 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 13.07 10:12:02, skipping insertion in model container [2022-07-13 10:12:02,932 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.07 10:12:02" (3/3) ... [2022-07-13 10:12:02,933 INFO L111 eAbstractionObserver]: Analyzing ICFG pnr5.c [2022-07-13 10:12:02,946 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-07-13 10:12:02,959 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-07-13 10:12:03,017 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-07-13 10:12:03,026 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@56a8a26c, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@77c9cb33 [2022-07-13 10:12:03,026 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-07-13 10:12:03,046 INFO L276 IsEmpty]: Start isEmpty. Operand has 37 states, 29 states have (on average 1.4827586206896552) internal successors, (43), 30 states have internal predecessors, (43), 5 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-07-13 10:12:03,054 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-07-13 10:12:03,055 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:03,055 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:03,057 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:03,062 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:03,062 INFO L85 PathProgramCache]: Analyzing trace with hash -1765780314, now seen corresponding path program 1 times [2022-07-13 10:12:03,070 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:03,071 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [553156484] [2022-07-13 10:12:03,071 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:03,072 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:03,205 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:03,264 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-13 10:12:03,265 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:03,265 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [553156484] [2022-07-13 10:12:03,266 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [553156484] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-13 10:12:03,266 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-13 10:12:03,266 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-07-13 10:12:03,268 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [16462054] [2022-07-13 10:12:03,268 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-13 10:12:03,273 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-07-13 10:12:03,274 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:03,303 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-07-13 10:12:03,304 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-13 10:12:03,307 INFO L87 Difference]: Start difference. First operand has 37 states, 29 states have (on average 1.4827586206896552) internal successors, (43), 30 states have internal predecessors, (43), 5 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-13 10:12:03,335 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:03,335 INFO L93 Difference]: Finished difference Result 69 states and 98 transitions. [2022-07-13 10:12:03,337 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-13 10:12:03,338 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2022-07-13 10:12:03,339 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:03,345 INFO L225 Difference]: With dead ends: 69 [2022-07-13 10:12:03,346 INFO L226 Difference]: Without dead ends: 33 [2022-07-13 10:12:03,374 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-13 10:12:03,393 INFO L413 NwaCegarLoop]: 49 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, 49 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 [2022-07-13 10:12:03,394 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-13 10:12:03,420 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-07-13 10:12:03,444 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-07-13 10:12:03,446 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 26 states have internal predecessors, (33), 5 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-07-13 10:12:03,448 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2022-07-13 10:12:03,450 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 11 [2022-07-13 10:12:03,450 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:03,450 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2022-07-13 10:12:03,451 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-13 10:12:03,451 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-07-13 10:12:03,453 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-07-13 10:12:03,453 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:03,453 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:03,453 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-07-13 10:12:03,454 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:03,454 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:03,454 INFO L85 PathProgramCache]: Analyzing trace with hash -1807338759, now seen corresponding path program 1 times [2022-07-13 10:12:03,455 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:03,455 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1462707901] [2022-07-13 10:12:03,456 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:03,456 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:03,481 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:03,652 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-13 10:12:03,652 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:03,652 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1462707901] [2022-07-13 10:12:03,653 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1462707901] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-13 10:12:03,653 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-13 10:12:03,653 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-13 10:12:03,653 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [494435806] [2022-07-13 10:12:03,654 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-13 10:12:03,655 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-13 10:12:03,655 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:03,656 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-13 10:12:03,656 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-07-13 10:12:03,657 INFO L87 Difference]: Start difference. First operand 33 states and 43 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-13 10:12:03,780 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:03,781 INFO L93 Difference]: Finished difference Result 57 states and 78 transitions. [2022-07-13 10:12:03,781 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-13 10:12:03,781 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2022-07-13 10:12:03,782 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:03,783 INFO L225 Difference]: With dead ends: 57 [2022-07-13 10:12:03,783 INFO L226 Difference]: Without dead ends: 50 [2022-07-13 10:12:03,783 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-07-13 10:12:03,785 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 121 mSDsluCounter, 12 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 126 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 77 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:03,785 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [126 Valid, 40 Invalid, 77 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-13 10:12:03,786 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-07-13 10:12:03,794 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 34. [2022-07-13 10:12:03,795 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 27 states have internal predecessors, (34), 5 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-07-13 10:12:03,796 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 44 transitions. [2022-07-13 10:12:03,796 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 44 transitions. Word has length 11 [2022-07-13 10:12:03,796 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:03,797 INFO L495 AbstractCegarLoop]: Abstraction has 34 states and 44 transitions. [2022-07-13 10:12:03,797 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-13 10:12:03,797 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 44 transitions. [2022-07-13 10:12:03,798 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-07-13 10:12:03,798 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:03,799 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:03,799 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-07-13 10:12:03,799 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:03,800 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:03,800 INFO L85 PathProgramCache]: Analyzing trace with hash 1950771071, now seen corresponding path program 1 times [2022-07-13 10:12:03,800 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:03,800 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [139268061] [2022-07-13 10:12:03,800 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:03,801 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:03,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:04,086 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:04,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:04,093 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:04,097 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:04,100 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:04,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:04,106 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:04,109 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:04,112 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:04,115 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:04,119 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:04,119 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:04,120 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [139268061] [2022-07-13 10:12:04,120 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [139268061] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:04,120 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1107705499] [2022-07-13 10:12:04,120 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:04,121 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:04,121 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:04,123 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-13 10:12:04,160 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-07-13 10:12:04,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:04,219 INFO L263 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 24 conjunts are in the unsatisfiable core [2022-07-13 10:12:04,227 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:04,311 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2022-07-13 10:12:04,341 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:04,342 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 29 [2022-07-13 10:12:04,372 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:04,373 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 29 [2022-07-13 10:12:04,408 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:04,409 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 29 [2022-07-13 10:12:04,465 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:04,466 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 21 [2022-07-13 10:12:04,535 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:04,535 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:12:04,670 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 13 [2022-07-13 10:12:04,674 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 22 [2022-07-13 10:12:04,691 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:04,691 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1107705499] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 10:12:04,692 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 10:12:04,692 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 6] total 12 [2022-07-13 10:12:04,692 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2072767999] [2022-07-13 10:12:04,692 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 10:12:04,693 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-07-13 10:12:04,693 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:04,694 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-07-13 10:12:04,694 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2022-07-13 10:12:04,694 INFO L87 Difference]: Start difference. First operand 34 states and 44 transitions. Second operand has 12 states, 12 states have (on average 4.0) internal successors, (48), 12 states have internal predecessors, (48), 4 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-07-13 10:12:05,036 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:05,037 INFO L93 Difference]: Finished difference Result 120 states and 171 transitions. [2022-07-13 10:12:05,037 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-07-13 10:12:05,037 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 4.0) internal successors, (48), 12 states have internal predecessors, (48), 4 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 43 [2022-07-13 10:12:05,038 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:05,039 INFO L225 Difference]: With dead ends: 120 [2022-07-13 10:12:05,039 INFO L226 Difference]: Without dead ends: 118 [2022-07-13 10:12:05,040 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 89 SyntacticMatches, 7 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=97, Invalid=245, Unknown=0, NotChecked=0, Total=342 [2022-07-13 10:12:05,041 INFO L413 NwaCegarLoop]: 60 mSDtfsCounter, 123 mSDsluCounter, 233 mSDsCounter, 0 mSdLazyCounter, 287 mSolverCounterSat, 102 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 137 SdHoareTripleChecker+Valid, 293 SdHoareTripleChecker+Invalid, 389 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 102 IncrementalHoareTripleChecker+Valid, 287 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:05,042 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [137 Valid, 293 Invalid, 389 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [102 Valid, 287 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-13 10:12:05,043 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2022-07-13 10:12:05,054 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 54. [2022-07-13 10:12:05,055 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 42 states have (on average 1.3095238095238095) internal successors, (55), 42 states have internal predecessors, (55), 10 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-07-13 10:12:05,056 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 75 transitions. [2022-07-13 10:12:05,056 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 75 transitions. Word has length 43 [2022-07-13 10:12:05,056 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:05,057 INFO L495 AbstractCegarLoop]: Abstraction has 54 states and 75 transitions. [2022-07-13 10:12:05,057 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 4.0) internal successors, (48), 12 states have internal predecessors, (48), 4 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-07-13 10:12:05,057 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 75 transitions. [2022-07-13 10:12:05,058 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-07-13 10:12:05,058 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:05,059 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:05,088 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-07-13 10:12:05,285 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:05,286 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:05,286 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:05,286 INFO L85 PathProgramCache]: Analyzing trace with hash -1642596351, now seen corresponding path program 1 times [2022-07-13 10:12:05,287 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:05,287 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [466386391] [2022-07-13 10:12:05,287 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:05,287 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:05,349 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:05,571 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:05,576 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:05,582 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:05,586 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:05,589 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:05,590 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:05,593 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:05,595 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:05,597 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:05,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:05,602 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:05,602 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:05,602 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [466386391] [2022-07-13 10:12:05,602 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [466386391] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:05,603 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [214334259] [2022-07-13 10:12:05,603 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:05,603 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:05,603 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:05,604 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-13 10:12:05,606 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-07-13 10:12:05,664 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:05,666 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 23 conjunts are in the unsatisfiable core [2022-07-13 10:12:05,670 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:05,749 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2022-07-13 10:12:05,831 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:05,832 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:12:05,890 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:05,891 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:12:05,945 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:05,946 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:12:06,005 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:06,006 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 20 [2022-07-13 10:12:06,060 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2022-07-13 10:12:06,109 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 12 proven. 1 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-07-13 10:12:06,110 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:12:06,285 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 13 [2022-07-13 10:12:06,289 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 26 [2022-07-13 10:12:06,347 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:06,347 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [214334259] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 10:12:06,347 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 10:12:06,348 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9, 7] total 19 [2022-07-13 10:12:06,348 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [269736596] [2022-07-13 10:12:06,348 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 10:12:06,349 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-07-13 10:12:06,349 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:06,349 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-07-13 10:12:06,350 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=279, Unknown=0, NotChecked=0, Total=342 [2022-07-13 10:12:06,350 INFO L87 Difference]: Start difference. First operand 54 states and 75 transitions. Second operand has 19 states, 19 states have (on average 3.473684210526316) internal successors, (66), 19 states have internal predecessors, (66), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2022-07-13 10:12:07,122 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:07,122 INFO L93 Difference]: Finished difference Result 179 states and 251 transitions. [2022-07-13 10:12:07,122 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2022-07-13 10:12:07,123 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 3.473684210526316) internal successors, (66), 19 states have internal predecessors, (66), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) Word has length 43 [2022-07-13 10:12:07,123 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:07,126 INFO L225 Difference]: With dead ends: 179 [2022-07-13 10:12:07,126 INFO L226 Difference]: Without dead ends: 177 [2022-07-13 10:12:07,127 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 77 SyntacticMatches, 12 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 405 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=258, Invalid=1074, Unknown=0, NotChecked=0, Total=1332 [2022-07-13 10:12:07,128 INFO L413 NwaCegarLoop]: 75 mSDtfsCounter, 145 mSDsluCounter, 441 mSDsCounter, 0 mSdLazyCounter, 643 mSolverCounterSat, 193 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 151 SdHoareTripleChecker+Valid, 516 SdHoareTripleChecker+Invalid, 930 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 193 IncrementalHoareTripleChecker+Valid, 643 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 94 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:07,128 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [151 Valid, 516 Invalid, 930 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [193 Valid, 643 Invalid, 0 Unknown, 94 Unchecked, 0.5s Time] [2022-07-13 10:12:07,129 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2022-07-13 10:12:07,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 87. [2022-07-13 10:12:07,146 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 64 states have (on average 1.359375) internal successors, (87), 65 states have internal predecessors, (87), 20 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2022-07-13 10:12:07,147 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 127 transitions. [2022-07-13 10:12:07,147 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 127 transitions. Word has length 43 [2022-07-13 10:12:07,148 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:07,148 INFO L495 AbstractCegarLoop]: Abstraction has 87 states and 127 transitions. [2022-07-13 10:12:07,148 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 3.473684210526316) internal successors, (66), 19 states have internal predecessors, (66), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2022-07-13 10:12:07,148 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 127 transitions. [2022-07-13 10:12:07,150 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-07-13 10:12:07,150 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:07,150 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:07,182 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-07-13 10:12:07,373 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,SelfDestructingSolverStorable3 [2022-07-13 10:12:07,373 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:07,374 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:07,374 INFO L85 PathProgramCache]: Analyzing trace with hash -1666037387, now seen corresponding path program 1 times [2022-07-13 10:12:07,374 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:07,374 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1481391334] [2022-07-13 10:12:07,374 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:07,375 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:07,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:07,569 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:07,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:07,575 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:07,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:07,579 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:07,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:07,582 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:07,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:07,587 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:07,590 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:07,597 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:07,597 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:07,598 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1481391334] [2022-07-13 10:12:07,598 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1481391334] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:07,598 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [877642089] [2022-07-13 10:12:07,598 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:07,598 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:07,600 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:07,601 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-13 10:12:07,607 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-07-13 10:12:07,664 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:07,665 INFO L263 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 24 conjunts are in the unsatisfiable core [2022-07-13 10:12:07,671 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:07,705 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2022-07-13 10:12:07,730 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:07,730 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 29 [2022-07-13 10:12:07,752 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:07,752 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 29 [2022-07-13 10:12:07,772 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:07,773 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 23 [2022-07-13 10:12:07,820 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:07,821 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:12:07,923 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 15 [2022-07-13 10:12:07,925 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 26 [2022-07-13 10:12:07,947 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:07,947 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [877642089] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 10:12:07,947 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 10:12:07,947 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 7] total 13 [2022-07-13 10:12:07,948 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [74809892] [2022-07-13 10:12:07,948 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 10:12:07,948 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-07-13 10:12:07,949 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:07,949 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-07-13 10:12:07,949 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2022-07-13 10:12:07,950 INFO L87 Difference]: Start difference. First operand 87 states and 127 transitions. Second operand has 13 states, 13 states have (on average 4.3076923076923075) internal successors, (56), 13 states have internal predecessors, (56), 4 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-07-13 10:12:08,389 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:08,389 INFO L93 Difference]: Finished difference Result 322 states and 492 transitions. [2022-07-13 10:12:08,389 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-07-13 10:12:08,390 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 4.3076923076923075) internal successors, (56), 13 states have internal predecessors, (56), 4 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 47 [2022-07-13 10:12:08,390 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:08,393 INFO L225 Difference]: With dead ends: 322 [2022-07-13 10:12:08,393 INFO L226 Difference]: Without dead ends: 320 [2022-07-13 10:12:08,394 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 95 SyntacticMatches, 8 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 118 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=131, Invalid=375, Unknown=0, NotChecked=0, Total=506 [2022-07-13 10:12:08,397 INFO L413 NwaCegarLoop]: 68 mSDtfsCounter, 147 mSDsluCounter, 277 mSDsCounter, 0 mSdLazyCounter, 362 mSolverCounterSat, 168 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 160 SdHoareTripleChecker+Valid, 345 SdHoareTripleChecker+Invalid, 530 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 168 IncrementalHoareTripleChecker+Valid, 362 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:08,398 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [160 Valid, 345 Invalid, 530 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [168 Valid, 362 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-13 10:12:08,401 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 320 states. [2022-07-13 10:12:08,449 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 320 to 153. [2022-07-13 10:12:08,451 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 153 states, 112 states have (on average 1.3928571428571428) internal successors, (156), 114 states have internal predecessors, (156), 38 states have call successors, (38), 2 states have call predecessors, (38), 2 states have return successors, (38), 36 states have call predecessors, (38), 38 states have call successors, (38) [2022-07-13 10:12:08,457 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 232 transitions. [2022-07-13 10:12:08,457 INFO L78 Accepts]: Start accepts. Automaton has 153 states and 232 transitions. Word has length 47 [2022-07-13 10:12:08,460 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:08,460 INFO L495 AbstractCegarLoop]: Abstraction has 153 states and 232 transitions. [2022-07-13 10:12:08,460 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 4.3076923076923075) internal successors, (56), 13 states have internal predecessors, (56), 4 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-07-13 10:12:08,461 INFO L276 IsEmpty]: Start isEmpty. Operand 153 states and 232 transitions. [2022-07-13 10:12:08,468 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-07-13 10:12:08,471 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:08,472 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:08,499 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-07-13 10:12:08,696 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 [2022-07-13 10:12:08,696 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:08,697 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:08,697 INFO L85 PathProgramCache]: Analyzing trace with hash -279833993, now seen corresponding path program 1 times [2022-07-13 10:12:08,697 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:08,697 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [154445867] [2022-07-13 10:12:08,697 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:08,697 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:08,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:08,897 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:08,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:08,901 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:08,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:08,904 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:08,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:08,907 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:08,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:08,910 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:08,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:08,913 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:08,914 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:08,914 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [154445867] [2022-07-13 10:12:08,914 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [154445867] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:08,914 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [189385073] [2022-07-13 10:12:08,914 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:08,915 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:08,915 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:08,916 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-13 10:12:08,935 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-07-13 10:12:08,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:08,979 INFO L263 TraceCheckSpWp]: Trace formula consists of 205 conjuncts, 23 conjunts are in the unsatisfiable core [2022-07-13 10:12:08,984 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:09,074 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2022-07-13 10:12:09,129 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:09,130 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:12:09,181 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:09,181 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:12:09,234 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:09,235 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 22 [2022-07-13 10:12:09,337 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2022-07-13 10:12:09,357 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 18 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-07-13 10:12:09,357 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:12:09,504 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 15 [2022-07-13 10:12:09,507 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 30 [2022-07-13 10:12:09,568 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:09,568 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [189385073] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 10:12:09,568 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 10:12:09,568 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 8] total 21 [2022-07-13 10:12:09,568 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [328369988] [2022-07-13 10:12:09,568 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 10:12:09,569 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-07-13 10:12:09,569 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:09,569 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-07-13 10:12:09,570 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=349, Unknown=0, NotChecked=0, Total=420 [2022-07-13 10:12:09,570 INFO L87 Difference]: Start difference. First operand 153 states and 232 transitions. Second operand has 21 states, 21 states have (on average 3.7142857142857144) internal successors, (78), 21 states have internal predecessors, (78), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2022-07-13 10:12:10,575 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:10,575 INFO L93 Difference]: Finished difference Result 462 states and 691 transitions. [2022-07-13 10:12:10,575 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2022-07-13 10:12:10,575 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 3.7142857142857144) internal successors, (78), 21 states have internal predecessors, (78), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) Word has length 47 [2022-07-13 10:12:10,576 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:10,578 INFO L225 Difference]: With dead ends: 462 [2022-07-13 10:12:10,578 INFO L226 Difference]: Without dead ends: 460 [2022-07-13 10:12:10,580 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 85 SyntacticMatches, 10 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 542 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=324, Invalid=1482, Unknown=0, NotChecked=0, Total=1806 [2022-07-13 10:12:10,580 INFO L413 NwaCegarLoop]: 92 mSDtfsCounter, 199 mSDsluCounter, 546 mSDsCounter, 0 mSdLazyCounter, 868 mSolverCounterSat, 276 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 206 SdHoareTripleChecker+Valid, 638 SdHoareTripleChecker+Invalid, 1247 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 276 IncrementalHoareTripleChecker+Valid, 868 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 103 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:10,581 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [206 Valid, 638 Invalid, 1247 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [276 Valid, 868 Invalid, 0 Unknown, 103 Unchecked, 0.6s Time] [2022-07-13 10:12:10,582 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 460 states. [2022-07-13 10:12:10,615 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 460 to 220. [2022-07-13 10:12:10,616 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 220 states, 158 states have (on average 1.4113924050632911) internal successors, (223), 161 states have internal predecessors, (223), 57 states have call successors, (57), 4 states have call predecessors, (57), 4 states have return successors, (57), 54 states have call predecessors, (57), 57 states have call successors, (57) [2022-07-13 10:12:10,617 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 220 states to 220 states and 337 transitions. [2022-07-13 10:12:10,617 INFO L78 Accepts]: Start accepts. Automaton has 220 states and 337 transitions. Word has length 47 [2022-07-13 10:12:10,618 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:10,618 INFO L495 AbstractCegarLoop]: Abstraction has 220 states and 337 transitions. [2022-07-13 10:12:10,618 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 3.7142857142857144) internal successors, (78), 21 states have internal predecessors, (78), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2022-07-13 10:12:10,618 INFO L276 IsEmpty]: Start isEmpty. Operand 220 states and 337 transitions. [2022-07-13 10:12:10,620 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-07-13 10:12:10,620 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:10,620 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:10,645 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2022-07-13 10:12:10,839 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 [2022-07-13 10:12:10,840 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:10,840 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:10,840 INFO L85 PathProgramCache]: Analyzing trace with hash 131088491, now seen corresponding path program 2 times [2022-07-13 10:12:10,840 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:10,840 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1780446890] [2022-07-13 10:12:10,840 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:10,841 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:10,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:10,929 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:10,930 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:10,932 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:10,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:10,934 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:10,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:10,937 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:10,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:10,939 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:10,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:10,943 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:10,943 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:10,943 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1780446890] [2022-07-13 10:12:10,944 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1780446890] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:10,944 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [197616797] [2022-07-13 10:12:10,944 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-13 10:12:10,944 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:10,944 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:10,948 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-13 10:12:10,974 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-07-13 10:12:11,022 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-13 10:12:11,022 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-13 10:12:11,024 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 28 conjunts are in the unsatisfiable core [2022-07-13 10:12:11,031 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:11,055 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2022-07-13 10:12:11,076 INFO L356 Elim1Store]: treesize reduction 42, result has 22.2 percent of original size [2022-07-13 10:12:11,077 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 29 [2022-07-13 10:12:11,101 INFO L356 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2022-07-13 10:12:11,101 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 23 [2022-07-13 10:12:11,158 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:11,158 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:12:11,228 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 15 [2022-07-13 10:12:11,230 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 26 [2022-07-13 10:12:11,263 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:11,263 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [197616797] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 10:12:11,264 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 10:12:11,264 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 8] total 12 [2022-07-13 10:12:11,264 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1517165744] [2022-07-13 10:12:11,264 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 10:12:11,264 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-07-13 10:12:11,265 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:11,265 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-07-13 10:12:11,265 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2022-07-13 10:12:11,266 INFO L87 Difference]: Start difference. First operand 220 states and 337 transitions. Second operand has 12 states, 12 states have (on average 4.416666666666667) internal successors, (53), 12 states have internal predecessors, (53), 3 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2022-07-13 10:12:12,046 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:12,046 INFO L93 Difference]: Finished difference Result 1182 states and 1872 transitions. [2022-07-13 10:12:12,046 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2022-07-13 10:12:12,047 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 4.416666666666667) internal successors, (53), 12 states have internal predecessors, (53), 3 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 51 [2022-07-13 10:12:12,047 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:12,053 INFO L225 Difference]: With dead ends: 1182 [2022-07-13 10:12:12,053 INFO L226 Difference]: Without dead ends: 1180 [2022-07-13 10:12:12,055 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 101 SyntacticMatches, 10 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 158 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=131, Invalid=519, Unknown=0, NotChecked=0, Total=650 [2022-07-13 10:12:12,056 INFO L413 NwaCegarLoop]: 122 mSDtfsCounter, 99 mSDsluCounter, 462 mSDsCounter, 0 mSdLazyCounter, 773 mSolverCounterSat, 178 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 119 SdHoareTripleChecker+Valid, 584 SdHoareTripleChecker+Invalid, 951 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 178 IncrementalHoareTripleChecker+Valid, 773 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:12,056 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [119 Valid, 584 Invalid, 951 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [178 Valid, 773 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-07-13 10:12:12,057 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1180 states. [2022-07-13 10:12:12,136 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1180 to 481. [2022-07-13 10:12:12,137 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 481 states, 346 states have (on average 1.4421965317919074) internal successors, (499), 349 states have internal predecessors, (499), 130 states have call successors, (130), 4 states have call predecessors, (130), 4 states have return successors, (130), 127 states have call predecessors, (130), 130 states have call successors, (130) [2022-07-13 10:12:12,139 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 481 states to 481 states and 759 transitions. [2022-07-13 10:12:12,140 INFO L78 Accepts]: Start accepts. Automaton has 481 states and 759 transitions. Word has length 51 [2022-07-13 10:12:12,140 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:12,140 INFO L495 AbstractCegarLoop]: Abstraction has 481 states and 759 transitions. [2022-07-13 10:12:12,141 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 4.416666666666667) internal successors, (53), 12 states have internal predecessors, (53), 3 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2022-07-13 10:12:12,141 INFO L276 IsEmpty]: Start isEmpty. Operand 481 states and 759 transitions. [2022-07-13 10:12:12,142 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-07-13 10:12:12,142 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:12,142 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:12,170 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-07-13 10:12:12,355 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 [2022-07-13 10:12:12,356 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:12,356 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:12,356 INFO L85 PathProgramCache]: Analyzing trace with hash 2054316525, now seen corresponding path program 1 times [2022-07-13 10:12:12,356 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:12,356 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [933462270] [2022-07-13 10:12:12,356 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:12,356 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:12,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:12,476 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:12,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:12,480 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:12,481 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:12,483 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:12,485 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:12,488 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:12,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:12,491 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:12,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:12,496 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:12,497 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:12,497 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [933462270] [2022-07-13 10:12:12,497 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [933462270] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:12,497 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2135213515] [2022-07-13 10:12:12,497 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:12,498 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:12,498 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:12,499 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-13 10:12:12,512 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-07-13 10:12:12,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:12,565 INFO L263 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 21 conjunts are in the unsatisfiable core [2022-07-13 10:12:12,568 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:12,658 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2022-07-13 10:12:12,730 INFO L356 Elim1Store]: treesize reduction 42, result has 22.2 percent of original size [2022-07-13 10:12:12,730 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:12:12,783 INFO L356 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2022-07-13 10:12:12,784 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 23 treesize of output 22 [2022-07-13 10:12:12,898 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 7 [2022-07-13 10:12:12,923 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 18 proven. 9 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-07-13 10:12:12,923 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:12:13,078 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 15 [2022-07-13 10:12:13,081 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 30 [2022-07-13 10:12:13,112 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2135213515] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:13,112 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-13 10:12:13,113 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 18 [2022-07-13 10:12:13,113 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1456054734] [2022-07-13 10:12:13,113 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-13 10:12:13,113 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-07-13 10:12:13,113 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:13,114 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-07-13 10:12:13,114 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=431, Unknown=0, NotChecked=0, Total=506 [2022-07-13 10:12:13,114 INFO L87 Difference]: Start difference. First operand 481 states and 759 transitions. Second operand has 18 states, 18 states have (on average 3.5) internal successors, (63), 18 states have internal predecessors, (63), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-07-13 10:12:14,227 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:14,227 INFO L93 Difference]: Finished difference Result 1217 states and 1879 transitions. [2022-07-13 10:12:14,228 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2022-07-13 10:12:14,228 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 3.5) internal successors, (63), 18 states have internal predecessors, (63), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 51 [2022-07-13 10:12:14,229 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:14,236 INFO L225 Difference]: With dead ends: 1217 [2022-07-13 10:12:14,236 INFO L226 Difference]: Without dead ends: 1215 [2022-07-13 10:12:14,238 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 73 SyntacticMatches, 7 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 706 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=370, Invalid=2080, Unknown=0, NotChecked=0, Total=2450 [2022-07-13 10:12:14,239 INFO L413 NwaCegarLoop]: 97 mSDtfsCounter, 237 mSDsluCounter, 510 mSDsCounter, 0 mSdLazyCounter, 750 mSolverCounterSat, 289 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 250 SdHoareTripleChecker+Valid, 607 SdHoareTripleChecker+Invalid, 1125 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 289 IncrementalHoareTripleChecker+Valid, 750 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 86 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:14,240 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [250 Valid, 607 Invalid, 1125 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [289 Valid, 750 Invalid, 0 Unknown, 86 Unchecked, 0.6s Time] [2022-07-13 10:12:14,242 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1215 states. [2022-07-13 10:12:14,323 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1215 to 646. [2022-07-13 10:12:14,324 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 646 states, 462 states have (on average 1.448051948051948) internal successors, (669), 465 states have internal predecessors, (669), 175 states have call successors, (175), 8 states have call predecessors, (175), 8 states have return successors, (175), 172 states have call predecessors, (175), 175 states have call successors, (175) [2022-07-13 10:12:14,328 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 646 states to 646 states and 1019 transitions. [2022-07-13 10:12:14,328 INFO L78 Accepts]: Start accepts. Automaton has 646 states and 1019 transitions. Word has length 51 [2022-07-13 10:12:14,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:14,329 INFO L495 AbstractCegarLoop]: Abstraction has 646 states and 1019 transitions. [2022-07-13 10:12:14,329 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 3.5) internal successors, (63), 18 states have internal predecessors, (63), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-07-13 10:12:14,329 INFO L276 IsEmpty]: Start isEmpty. Operand 646 states and 1019 transitions. [2022-07-13 10:12:14,331 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-07-13 10:12:14,331 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:14,331 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:14,355 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-07-13 10:12:14,553 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 [2022-07-13 10:12:14,553 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:14,554 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:14,554 INFO L85 PathProgramCache]: Analyzing trace with hash 881708129, now seen corresponding path program 3 times [2022-07-13 10:12:14,554 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:14,554 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [474726675] [2022-07-13 10:12:14,554 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:14,554 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:14,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:14,703 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:14,706 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:14,711 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:14,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:14,714 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:14,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:14,716 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:14,718 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:14,719 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:14,721 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:14,723 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 0 proven. 19 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:14,724 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:14,724 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [474726675] [2022-07-13 10:12:14,724 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [474726675] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:14,724 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1230513270] [2022-07-13 10:12:14,724 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-13 10:12:14,724 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:14,725 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:14,726 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-13 10:12:14,750 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-07-13 10:12:14,791 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-07-13 10:12:14,792 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-13 10:12:14,793 INFO L263 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 24 conjunts are in the unsatisfiable core [2022-07-13 10:12:14,794 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:14,843 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2022-07-13 10:12:16,973 INFO L356 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2022-07-13 10:12:16,974 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 23 [2022-07-13 10:12:17,171 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 12 proven. 19 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-07-13 10:12:17,171 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:12:25,769 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2022-07-13 10:12:25,771 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 32 [2022-07-13 10:12:25,794 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1230513270] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:25,794 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-13 10:12:25,794 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 19 [2022-07-13 10:12:25,794 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2070513215] [2022-07-13 10:12:25,794 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-13 10:12:25,795 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-07-13 10:12:25,795 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:25,795 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-07-13 10:12:25,796 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=500, Unknown=5, NotChecked=0, Total=600 [2022-07-13 10:12:25,796 INFO L87 Difference]: Start difference. First operand 646 states and 1019 transitions. Second operand has 19 states, 19 states have (on average 3.736842105263158) internal successors, (71), 19 states have internal predecessors, (71), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-07-13 10:12:28,821 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:28,821 INFO L93 Difference]: Finished difference Result 1980 states and 3113 transitions. [2022-07-13 10:12:28,823 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-07-13 10:12:28,823 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 3.736842105263158) internal successors, (71), 19 states have internal predecessors, (71), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 55 [2022-07-13 10:12:28,824 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:28,833 INFO L225 Difference]: With dead ends: 1980 [2022-07-13 10:12:28,833 INFO L226 Difference]: Without dead ends: 1978 [2022-07-13 10:12:28,836 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 81 SyntacticMatches, 15 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 584 ImplicationChecksByTransitivity, 13.2s TimeCoverageRelationStatistics Valid=339, Invalid=1461, Unknown=6, NotChecked=0, Total=1806 [2022-07-13 10:12:28,836 INFO L413 NwaCegarLoop]: 90 mSDtfsCounter, 277 mSDsluCounter, 500 mSDsCounter, 0 mSdLazyCounter, 535 mSolverCounterSat, 182 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 277 SdHoareTripleChecker+Valid, 590 SdHoareTripleChecker+Invalid, 815 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 182 IncrementalHoareTripleChecker+Valid, 535 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 98 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:28,837 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [277 Valid, 590 Invalid, 815 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [182 Valid, 535 Invalid, 0 Unknown, 98 Unchecked, 0.4s Time] [2022-07-13 10:12:28,839 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1978 states. [2022-07-13 10:12:29,014 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1978 to 1372. [2022-07-13 10:12:29,016 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1372 states, 980 states have (on average 1.4551020408163264) internal successors, (1426), 983 states have internal predecessors, (1426), 375 states have call successors, (375), 16 states have call predecessors, (375), 16 states have return successors, (375), 372 states have call predecessors, (375), 375 states have call successors, (375) [2022-07-13 10:12:29,022 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1372 states to 1372 states and 2176 transitions. [2022-07-13 10:12:29,022 INFO L78 Accepts]: Start accepts. Automaton has 1372 states and 2176 transitions. Word has length 55 [2022-07-13 10:12:29,023 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:29,023 INFO L495 AbstractCegarLoop]: Abstraction has 1372 states and 2176 transitions. [2022-07-13 10:12:29,024 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 3.736842105263158) internal successors, (71), 19 states have internal predecessors, (71), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-07-13 10:12:29,024 INFO L276 IsEmpty]: Start isEmpty. Operand 1372 states and 2176 transitions. [2022-07-13 10:12:29,028 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-07-13 10:12:29,028 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:29,028 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:29,058 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-07-13 10:12:29,255 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 [2022-07-13 10:12:29,255 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:29,256 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:29,256 INFO L85 PathProgramCache]: Analyzing trace with hash 1022256739, now seen corresponding path program 1 times [2022-07-13 10:12:29,256 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:29,256 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1222172931] [2022-07-13 10:12:29,256 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:29,256 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:29,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:29,418 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:29,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:29,421 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:29,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:29,423 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:29,424 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:29,426 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:29,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:29,428 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:29,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:29,430 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 0 proven. 19 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:29,431 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:29,431 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1222172931] [2022-07-13 10:12:29,431 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1222172931] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:29,431 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1460535372] [2022-07-13 10:12:29,431 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:29,431 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:29,432 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:29,433 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) [2022-07-13 10:12:29,464 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-07-13 10:12:29,509 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:29,510 INFO L263 TraceCheckSpWp]: Trace formula consists of 227 conjuncts, 21 conjunts are in the unsatisfiable core [2022-07-13 10:12:29,513 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:29,603 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2022-07-13 10:12:29,673 INFO L356 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2022-07-13 10:12:29,674 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 23 treesize of output 22 [2022-07-13 10:12:29,798 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 7 [2022-07-13 10:12:29,823 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 12 proven. 19 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-07-13 10:12:29,823 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:12:31,960 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 15 [2022-07-13 10:12:31,962 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 30 [2022-07-13 10:12:32,010 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1460535372] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:32,010 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-13 10:12:32,010 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 19 [2022-07-13 10:12:32,010 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1179004841] [2022-07-13 10:12:32,010 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-13 10:12:32,011 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-07-13 10:12:32,011 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:32,011 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-07-13 10:12:32,011 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=523, Unknown=1, NotChecked=0, Total=600 [2022-07-13 10:12:32,012 INFO L87 Difference]: Start difference. First operand 1372 states and 2176 transitions. Second operand has 19 states, 19 states have (on average 3.736842105263158) internal successors, (71), 19 states have internal predecessors, (71), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-07-13 10:12:33,768 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:33,769 INFO L93 Difference]: Finished difference Result 3737 states and 5871 transitions. [2022-07-13 10:12:33,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2022-07-13 10:12:33,769 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 3.736842105263158) internal successors, (71), 19 states have internal predecessors, (71), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 55 [2022-07-13 10:12:33,769 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:33,789 INFO L225 Difference]: With dead ends: 3737 [2022-07-13 10:12:33,789 INFO L226 Difference]: Without dead ends: 3735 [2022-07-13 10:12:33,793 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 140 GetRequests, 81 SyntacticMatches, 5 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 820 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=385, Invalid=2694, Unknown=1, NotChecked=0, Total=3080 [2022-07-13 10:12:33,794 INFO L413 NwaCegarLoop]: 126 mSDtfsCounter, 223 mSDsluCounter, 709 mSDsCounter, 0 mSdLazyCounter, 1136 mSolverCounterSat, 281 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 229 SdHoareTripleChecker+Valid, 835 SdHoareTripleChecker+Invalid, 1558 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 281 IncrementalHoareTripleChecker+Valid, 1136 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 141 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:33,795 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [229 Valid, 835 Invalid, 1558 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [281 Valid, 1136 Invalid, 0 Unknown, 141 Unchecked, 0.7s Time] [2022-07-13 10:12:33,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3735 states. [2022-07-13 10:12:34,081 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3735 to 1856. [2022-07-13 10:12:34,085 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1856 states, 1320 states have (on average 1.4606060606060607) internal successors, (1928), 1324 states have internal predecessors, (1928), 511 states have call successors, (511), 24 states have call predecessors, (511), 24 states have return successors, (511), 507 states have call predecessors, (511), 511 states have call successors, (511) [2022-07-13 10:12:34,093 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1856 states to 1856 states and 2950 transitions. [2022-07-13 10:12:34,093 INFO L78 Accepts]: Start accepts. Automaton has 1856 states and 2950 transitions. Word has length 55 [2022-07-13 10:12:34,094 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:34,094 INFO L495 AbstractCegarLoop]: Abstraction has 1856 states and 2950 transitions. [2022-07-13 10:12:34,094 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 3.736842105263158) internal successors, (71), 19 states have internal predecessors, (71), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-07-13 10:12:34,094 INFO L276 IsEmpty]: Start isEmpty. Operand 1856 states and 2950 transitions. [2022-07-13 10:12:34,096 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2022-07-13 10:12:34,097 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:34,097 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:34,116 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-07-13 10:12:34,305 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 [2022-07-13 10:12:34,305 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:34,305 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:34,305 INFO L85 PathProgramCache]: Analyzing trace with hash 1863871831, now seen corresponding path program 4 times [2022-07-13 10:12:34,305 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:34,306 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [641325796] [2022-07-13 10:12:34,306 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:34,306 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:34,333 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:34,442 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:34,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:34,451 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:34,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:34,454 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:34,456 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:34,457 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:34,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:34,459 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:34,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:34,461 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:34,461 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:34,461 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [641325796] [2022-07-13 10:12:34,461 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [641325796] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:34,462 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [768656712] [2022-07-13 10:12:34,462 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-13 10:12:34,462 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:34,462 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:34,464 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) [2022-07-13 10:12:34,490 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-07-13 10:12:34,541 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-13 10:12:34,541 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-13 10:12:34,543 INFO L263 TraceCheckSpWp]: Trace formula consists of 237 conjuncts, 22 conjunts are in the unsatisfiable core [2022-07-13 10:12:34,546 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:34,570 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2022-07-13 10:12:34,660 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:34,660 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:12:34,708 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 15 [2022-07-13 10:12:34,710 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 26 [2022-07-13 10:12:34,739 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:34,740 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [768656712] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 10:12:34,740 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 10:12:34,740 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10, 10] total 16 [2022-07-13 10:12:34,740 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [652892819] [2022-07-13 10:12:34,740 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 10:12:34,741 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-07-13 10:12:34,741 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:34,741 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-07-13 10:12:34,741 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2022-07-13 10:12:34,742 INFO L87 Difference]: Start difference. First operand 1856 states and 2950 transitions. Second operand has 16 states, 16 states have (on average 4.0) internal successors, (64), 16 states have internal predecessors, (64), 1 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-07-13 10:12:38,894 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:38,894 INFO L93 Difference]: Finished difference Result 15973 states and 25766 transitions. [2022-07-13 10:12:38,894 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 80 states. [2022-07-13 10:12:38,894 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 4.0) internal successors, (64), 16 states have internal predecessors, (64), 1 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 59 [2022-07-13 10:12:38,895 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:38,977 INFO L225 Difference]: With dead ends: 15973 [2022-07-13 10:12:38,977 INFO L226 Difference]: Without dead ends: 15971 [2022-07-13 10:12:38,993 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 119 SyntacticMatches, 4 SemanticMatches, 82 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2480 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=777, Invalid=6195, Unknown=0, NotChecked=0, Total=6972 [2022-07-13 10:12:38,993 INFO L413 NwaCegarLoop]: 328 mSDtfsCounter, 293 mSDsluCounter, 1328 mSDsCounter, 0 mSdLazyCounter, 2931 mSolverCounterSat, 800 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 323 SdHoareTripleChecker+Valid, 1656 SdHoareTripleChecker+Invalid, 3731 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 800 IncrementalHoareTripleChecker+Valid, 2931 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:38,994 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [323 Valid, 1656 Invalid, 3731 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [800 Valid, 2931 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2022-07-13 10:12:39,010 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15971 states. [2022-07-13 10:12:40,190 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15971 to 5959. [2022-07-13 10:12:40,200 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5959 states, 4222 states have (on average 1.4819990525817148) internal successors, (6257), 4222 states have internal predecessors, (6257), 1712 states have call successors, (1712), 24 states have call predecessors, (1712), 24 states have return successors, (1712), 1712 states have call predecessors, (1712), 1712 states have call successors, (1712) [2022-07-13 10:12:40,217 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5959 states to 5959 states and 9681 transitions. [2022-07-13 10:12:40,217 INFO L78 Accepts]: Start accepts. Automaton has 5959 states and 9681 transitions. Word has length 59 [2022-07-13 10:12:40,218 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:40,218 INFO L495 AbstractCegarLoop]: Abstraction has 5959 states and 9681 transitions. [2022-07-13 10:12:40,218 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 4.0) internal successors, (64), 16 states have internal predecessors, (64), 1 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-07-13 10:12:40,218 INFO L276 IsEmpty]: Start isEmpty. Operand 5959 states and 9681 transitions. [2022-07-13 10:12:40,222 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2022-07-13 10:12:40,222 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:40,222 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:40,252 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-07-13 10:12:40,447 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 [2022-07-13 10:12:40,447 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:40,448 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:40,448 INFO L85 PathProgramCache]: Analyzing trace with hash 58433497, now seen corresponding path program 1 times [2022-07-13 10:12:40,448 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:40,448 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1108019894] [2022-07-13 10:12:40,448 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:40,448 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:40,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:40,584 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:40,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:40,587 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:40,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:40,589 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:40,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:40,592 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:40,593 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:40,594 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:40,595 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:40,596 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:40,597 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:40,597 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1108019894] [2022-07-13 10:12:40,597 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1108019894] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:40,597 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1902516455] [2022-07-13 10:12:40,597 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:40,597 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:40,597 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:40,599 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) [2022-07-13 10:12:40,622 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-07-13 10:12:40,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:40,673 INFO L263 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 21 conjunts are in the unsatisfiable core [2022-07-13 10:12:40,675 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:40,784 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2022-07-13 10:12:40,973 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 7 [2022-07-13 10:12:40,998 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:40,999 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:12:41,148 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 15 [2022-07-13 10:12:41,150 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 30 [2022-07-13 10:12:41,190 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1902516455] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:41,190 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-13 10:12:41,190 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 21 [2022-07-13 10:12:41,191 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1623270155] [2022-07-13 10:12:41,191 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-13 10:12:41,191 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-07-13 10:12:41,191 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:41,192 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-07-13 10:12:41,192 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=663, Unknown=0, NotChecked=0, Total=756 [2022-07-13 10:12:41,192 INFO L87 Difference]: Start difference. First operand 5959 states and 9681 transitions. Second operand has 21 states, 21 states have (on average 3.6666666666666665) internal successors, (77), 21 states have internal predecessors, (77), 2 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-07-13 10:12:44,819 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:44,819 INFO L93 Difference]: Finished difference Result 11693 states and 18784 transitions. [2022-07-13 10:12:44,823 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2022-07-13 10:12:44,823 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 3.6666666666666665) internal successors, (77), 21 states have internal predecessors, (77), 2 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 59 [2022-07-13 10:12:44,824 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:44,853 INFO L225 Difference]: With dead ends: 11693 [2022-07-13 10:12:44,853 INFO L226 Difference]: Without dead ends: 11691 [2022-07-13 10:12:44,863 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 78 SyntacticMatches, 1 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2004 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=1049, Invalid=5757, Unknown=0, NotChecked=0, Total=6806 [2022-07-13 10:12:44,863 INFO L413 NwaCegarLoop]: 137 mSDtfsCounter, 348 mSDsluCounter, 785 mSDsCounter, 0 mSdLazyCounter, 1553 mSolverCounterSat, 634 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 348 SdHoareTripleChecker+Valid, 922 SdHoareTripleChecker+Invalid, 2187 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 634 IncrementalHoareTripleChecker+Valid, 1553 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:44,864 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [348 Valid, 922 Invalid, 2187 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [634 Valid, 1553 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2022-07-13 10:12:44,873 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11691 states. [2022-07-13 10:12:45,348 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11691 to 1904. [2022-07-13 10:12:45,352 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1904 states, 1368 states have (on average 1.4502923976608186) internal successors, (1984), 1372 states have internal predecessors, (1984), 511 states have call successors, (511), 24 states have call predecessors, (511), 24 states have return successors, (511), 507 states have call predecessors, (511), 511 states have call successors, (511) [2022-07-13 10:12:45,357 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1904 states to 1904 states and 3006 transitions. [2022-07-13 10:12:45,357 INFO L78 Accepts]: Start accepts. Automaton has 1904 states and 3006 transitions. Word has length 59 [2022-07-13 10:12:45,358 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:45,358 INFO L495 AbstractCegarLoop]: Abstraction has 1904 states and 3006 transitions. [2022-07-13 10:12:45,358 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 3.6666666666666665) internal successors, (77), 21 states have internal predecessors, (77), 2 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-07-13 10:12:45,358 INFO L276 IsEmpty]: Start isEmpty. Operand 1904 states and 3006 transitions. [2022-07-13 10:12:45,361 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2022-07-13 10:12:45,361 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:45,361 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:45,385 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2022-07-13 10:12:45,575 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 [2022-07-13 10:12:45,575 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:45,576 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:45,576 INFO L85 PathProgramCache]: Analyzing trace with hash 819831629, now seen corresponding path program 5 times [2022-07-13 10:12:45,576 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:45,576 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1526300873] [2022-07-13 10:12:45,576 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:45,576 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:45,594 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:45,889 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:45,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:45,891 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:45,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:45,893 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:45,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:45,895 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:45,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:45,898 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:45,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:45,900 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 33 proven. 18 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:45,901 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:45,901 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1526300873] [2022-07-13 10:12:45,901 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1526300873] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:45,901 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [705993385] [2022-07-13 10:12:45,901 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-13 10:12:45,901 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:45,901 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:45,904 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) [2022-07-13 10:12:45,931 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-07-13 10:12:46,050 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2022-07-13 10:12:46,050 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-13 10:12:46,052 INFO L263 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-13 10:12:46,053 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:46,552 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 50 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:46,553 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:12:46,842 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 50 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-13 10:12:46,843 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [705993385] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 10:12:46,843 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 10:12:46,843 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 12] total 34 [2022-07-13 10:12:46,843 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [56391091] [2022-07-13 10:12:46,843 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 10:12:46,844 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2022-07-13 10:12:46,844 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:46,844 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2022-07-13 10:12:46,845 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=287, Invalid=835, Unknown=0, NotChecked=0, Total=1122 [2022-07-13 10:12:46,845 INFO L87 Difference]: Start difference. First operand 1904 states and 3006 transitions. Second operand has 34 states, 34 states have (on average 3.676470588235294) internal successors, (125), 34 states have internal predecessors, (125), 3 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2022-07-13 10:12:47,567 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:47,567 INFO L93 Difference]: Finished difference Result 2207 states and 3461 transitions. [2022-07-13 10:12:47,568 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-07-13 10:12:47,568 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 34 states have (on average 3.676470588235294) internal successors, (125), 34 states have internal predecessors, (125), 3 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) Word has length 63 [2022-07-13 10:12:47,568 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:47,579 INFO L225 Difference]: With dead ends: 2207 [2022-07-13 10:12:47,580 INFO L226 Difference]: Without dead ends: 2179 [2022-07-13 10:12:47,582 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 115 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 473 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=383, Invalid=1099, Unknown=0, NotChecked=0, Total=1482 [2022-07-13 10:12:47,582 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 293 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 485 mSolverCounterSat, 150 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 298 SdHoareTripleChecker+Valid, 204 SdHoareTripleChecker+Invalid, 635 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 150 IncrementalHoareTripleChecker+Valid, 485 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:47,583 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [298 Valid, 204 Invalid, 635 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [150 Valid, 485 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-13 10:12:47,585 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2179 states. [2022-07-13 10:12:48,011 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2179 to 1920. [2022-07-13 10:12:48,014 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1920 states, 1384 states have (on average 1.439306358381503) internal successors, (1992), 1384 states have internal predecessors, (1992), 511 states have call successors, (511), 24 states have call predecessors, (511), 24 states have return successors, (511), 511 states have call predecessors, (511), 511 states have call successors, (511) [2022-07-13 10:12:48,019 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1920 states to 1920 states and 3014 transitions. [2022-07-13 10:12:48,019 INFO L78 Accepts]: Start accepts. Automaton has 1920 states and 3014 transitions. Word has length 63 [2022-07-13 10:12:48,020 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:48,020 INFO L495 AbstractCegarLoop]: Abstraction has 1920 states and 3014 transitions. [2022-07-13 10:12:48,020 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 34 states have (on average 3.676470588235294) internal successors, (125), 34 states have internal predecessors, (125), 3 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2022-07-13 10:12:48,020 INFO L276 IsEmpty]: Start isEmpty. Operand 1920 states and 3014 transitions. [2022-07-13 10:12:48,023 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-07-13 10:12:48,024 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:48,024 INFO L195 NwaCegarLoop]: trace histogram [10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 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] [2022-07-13 10:12:48,029 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-07-13 10:12:48,228 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 [2022-07-13 10:12:48,229 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:48,229 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:48,229 INFO L85 PathProgramCache]: Analyzing trace with hash 374578441, now seen corresponding path program 2 times [2022-07-13 10:12:48,229 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:48,229 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2121806439] [2022-07-13 10:12:48,229 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:48,230 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:48,250 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:48,431 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:48,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:48,434 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:48,435 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:48,436 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:48,438 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:48,439 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:48,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:48,441 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:48,443 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:48,444 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2022-07-13 10:12:48,445 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:48,446 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 45 [2022-07-13 10:12:48,448 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:48,449 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2022-07-13 10:12:48,450 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:48,452 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 57 [2022-07-13 10:12:48,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:48,454 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2022-07-13 10:12:48,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:48,457 INFO L134 CoverageAnalysis]: Checked inductivity of 154 backedges. 0 proven. 19 refuted. 0 times theorem prover too weak. 135 trivial. 0 not checked. [2022-07-13 10:12:48,457 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:48,457 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2121806439] [2022-07-13 10:12:48,457 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2121806439] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:48,457 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [284572571] [2022-07-13 10:12:48,458 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-13 10:12:48,458 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:48,458 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:48,460 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) [2022-07-13 10:12:48,487 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-07-13 10:12:48,548 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-13 10:12:48,549 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-13 10:12:48,550 INFO L263 TraceCheckSpWp]: Trace formula consists of 303 conjuncts, 34 conjunts are in the unsatisfiable core [2022-07-13 10:12:48,554 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:48,623 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2022-07-13 10:12:48,695 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:48,696 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:12:48,749 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:48,750 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:12:48,804 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:48,805 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:12:48,863 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:48,863 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:12:48,946 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:48,947 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 23 [2022-07-13 10:12:48,996 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:48,997 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 23 [2022-07-13 10:12:49,059 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:49,060 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 23 [2022-07-13 10:12:49,119 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:49,120 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 23 [2022-07-13 10:12:49,177 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:49,179 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 23 [2022-07-13 10:12:49,238 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2022-07-13 10:12:49,261 INFO L134 CoverageAnalysis]: Checked inductivity of 154 backedges. 27 proven. 19 refuted. 0 times theorem prover too weak. 108 trivial. 0 not checked. [2022-07-13 10:12:49,261 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:12:49,431 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [284572571] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:49,431 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-13 10:12:49,431 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10] total 17 [2022-07-13 10:12:49,431 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2143781794] [2022-07-13 10:12:49,431 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-13 10:12:49,433 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-07-13 10:12:49,433 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:49,433 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-07-13 10:12:49,433 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=318, Unknown=0, NotChecked=0, Total=380 [2022-07-13 10:12:49,434 INFO L87 Difference]: Start difference. First operand 1920 states and 3014 transitions. Second operand has 17 states, 17 states have (on average 4.176470588235294) internal successors, (71), 17 states have internal predecessors, (71), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2022-07-13 10:12:50,898 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:50,898 INFO L93 Difference]: Finished difference Result 3981 states and 6220 transitions. [2022-07-13 10:12:50,898 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2022-07-13 10:12:50,899 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 4.176470588235294) internal successors, (71), 17 states have internal predecessors, (71), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) Word has length 75 [2022-07-13 10:12:50,899 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:50,912 INFO L225 Difference]: With dead ends: 3981 [2022-07-13 10:12:50,912 INFO L226 Difference]: Without dead ends: 3979 [2022-07-13 10:12:50,915 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 107 SyntacticMatches, 22 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 503 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=279, Invalid=1443, Unknown=0, NotChecked=0, Total=1722 [2022-07-13 10:12:50,916 INFO L413 NwaCegarLoop]: 91 mSDtfsCounter, 162 mSDsluCounter, 483 mSDsCounter, 0 mSdLazyCounter, 696 mSolverCounterSat, 222 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 164 SdHoareTripleChecker+Valid, 574 SdHoareTripleChecker+Invalid, 1012 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 222 IncrementalHoareTripleChecker+Valid, 696 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 94 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:50,916 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [164 Valid, 574 Invalid, 1012 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [222 Valid, 696 Invalid, 0 Unknown, 94 Unchecked, 0.4s Time] [2022-07-13 10:12:50,920 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3979 states. [2022-07-13 10:12:51,510 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3979 to 2319. [2022-07-13 10:12:51,513 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2319 states, 1668 states have (on average 1.4490407673860912) internal successors, (2417), 1668 states have internal predecessors, (2417), 625 states have call successors, (625), 25 states have call predecessors, (625), 25 states have return successors, (625), 625 states have call predecessors, (625), 625 states have call successors, (625) [2022-07-13 10:12:51,518 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2319 states to 2319 states and 3667 transitions. [2022-07-13 10:12:51,519 INFO L78 Accepts]: Start accepts. Automaton has 2319 states and 3667 transitions. Word has length 75 [2022-07-13 10:12:51,519 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:51,519 INFO L495 AbstractCegarLoop]: Abstraction has 2319 states and 3667 transitions. [2022-07-13 10:12:51,520 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 4.176470588235294) internal successors, (71), 17 states have internal predecessors, (71), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2022-07-13 10:12:51,520 INFO L276 IsEmpty]: Start isEmpty. Operand 2319 states and 3667 transitions. [2022-07-13 10:12:51,523 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2022-07-13 10:12:51,523 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:51,523 INFO L195 NwaCegarLoop]: trace histogram [10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1] [2022-07-13 10:12:51,551 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-07-13 10:12:51,750 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 [2022-07-13 10:12:51,751 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:51,751 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:51,751 INFO L85 PathProgramCache]: Analyzing trace with hash -1525924609, now seen corresponding path program 2 times [2022-07-13 10:12:51,751 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:51,751 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1267851751] [2022-07-13 10:12:51,751 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:51,751 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:51,780 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:51,987 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:51,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:51,990 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:51,991 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:51,994 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:51,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:51,999 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:52,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:52,005 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:52,006 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:52,008 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2022-07-13 10:12:52,009 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:52,010 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 45 [2022-07-13 10:12:52,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:52,013 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2022-07-13 10:12:52,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:52,015 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 57 [2022-07-13 10:12:52,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:52,017 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2022-07-13 10:12:52,018 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:52,019 INFO L134 CoverageAnalysis]: Checked inductivity of 156 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 135 trivial. 0 not checked. [2022-07-13 10:12:52,020 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:52,020 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1267851751] [2022-07-13 10:12:52,020 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1267851751] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:52,020 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2128344418] [2022-07-13 10:12:52,020 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-13 10:12:52,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:52,021 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:52,022 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) [2022-07-13 10:12:52,024 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-07-13 10:12:52,108 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-13 10:12:52,109 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-13 10:12:52,110 INFO L263 TraceCheckSpWp]: Trace formula consists of 314 conjuncts, 34 conjunts are in the unsatisfiable core [2022-07-13 10:12:52,113 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:52,184 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2022-07-13 10:12:52,249 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:52,249 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:12:52,295 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:52,296 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:12:52,343 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:52,343 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:12:52,410 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:52,410 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 25 [2022-07-13 10:12:52,455 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:52,455 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 25 [2022-07-13 10:12:52,501 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:52,501 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 25 [2022-07-13 10:12:52,545 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:52,546 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 25 [2022-07-13 10:12:52,600 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-13 10:12:52,600 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 25 [2022-07-13 10:12:52,693 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2022-07-13 10:12:52,718 INFO L134 CoverageAnalysis]: Checked inductivity of 156 backedges. 48 proven. 21 refuted. 0 times theorem prover too weak. 87 trivial. 0 not checked. [2022-07-13 10:12:52,718 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:12:52,931 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2128344418] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:52,931 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-13 10:12:52,931 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 18 [2022-07-13 10:12:52,931 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [472150563] [2022-07-13 10:12:52,931 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-13 10:12:52,932 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-07-13 10:12:52,932 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:12:52,932 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-07-13 10:12:52,932 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=392, Unknown=0, NotChecked=0, Total=462 [2022-07-13 10:12:52,933 INFO L87 Difference]: Start difference. First operand 2319 states and 3667 transitions. Second operand has 18 states, 18 states have (on average 4.388888888888889) internal successors, (79), 18 states have internal predecessors, (79), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2022-07-13 10:12:54,353 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:12:54,354 INFO L93 Difference]: Finished difference Result 3367 states and 5272 transitions. [2022-07-13 10:12:54,354 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2022-07-13 10:12:54,354 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 4.388888888888889) internal successors, (79), 18 states have internal predecessors, (79), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) Word has length 79 [2022-07-13 10:12:54,355 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:12:54,366 INFO L225 Difference]: With dead ends: 3367 [2022-07-13 10:12:54,366 INFO L226 Difference]: Without dead ends: 3365 [2022-07-13 10:12:54,368 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 113 SyntacticMatches, 20 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 661 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=340, Invalid=1822, Unknown=0, NotChecked=0, Total=2162 [2022-07-13 10:12:54,368 INFO L413 NwaCegarLoop]: 92 mSDtfsCounter, 215 mSDsluCounter, 410 mSDsCounter, 0 mSdLazyCounter, 637 mSolverCounterSat, 239 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 217 SdHoareTripleChecker+Valid, 502 SdHoareTripleChecker+Invalid, 988 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 239 IncrementalHoareTripleChecker+Valid, 637 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 112 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-07-13 10:12:54,368 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [217 Valid, 502 Invalid, 988 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [239 Valid, 637 Invalid, 0 Unknown, 112 Unchecked, 0.4s Time] [2022-07-13 10:12:54,371 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3365 states. [2022-07-13 10:12:54,959 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3365 to 2333. [2022-07-13 10:12:54,962 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2333 states, 1672 states have (on average 1.4479665071770336) internal successors, (2421), 1680 states have internal predecessors, (2421), 633 states have call successors, (633), 27 states have call predecessors, (633), 27 states have return successors, (633), 625 states have call predecessors, (633), 633 states have call successors, (633) [2022-07-13 10:12:54,968 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2333 states to 2333 states and 3687 transitions. [2022-07-13 10:12:54,968 INFO L78 Accepts]: Start accepts. Automaton has 2333 states and 3687 transitions. Word has length 79 [2022-07-13 10:12:54,968 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:12:54,968 INFO L495 AbstractCegarLoop]: Abstraction has 2333 states and 3687 transitions. [2022-07-13 10:12:54,969 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 4.388888888888889) internal successors, (79), 18 states have internal predecessors, (79), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2022-07-13 10:12:54,969 INFO L276 IsEmpty]: Start isEmpty. Operand 2333 states and 3687 transitions. [2022-07-13 10:12:54,974 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2022-07-13 10:12:54,974 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:12:54,974 INFO L195 NwaCegarLoop]: trace histogram [10, 10, 6, 5, 5, 5, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:12:55,002 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-07-13 10:12:55,199 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 [2022-07-13 10:12:55,199 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:12:55,200 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:12:55,200 INFO L85 PathProgramCache]: Analyzing trace with hash -375078701, now seen corresponding path program 6 times [2022-07-13 10:12:55,200 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:12:55,200 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1987524925] [2022-07-13 10:12:55,200 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:12:55,200 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:12:55,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:55,357 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:12:55,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:55,360 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:12:55,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:55,362 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:12:55,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:55,364 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:12:55,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:55,365 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:12:55,368 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:55,369 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2022-07-13 10:12:55,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:55,371 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 45 [2022-07-13 10:12:55,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:55,374 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2022-07-13 10:12:55,375 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:55,376 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 57 [2022-07-13 10:12:55,380 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:55,384 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2022-07-13 10:12:55,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:12:55,395 INFO L134 CoverageAnalysis]: Checked inductivity of 204 backedges. 0 proven. 69 refuted. 0 times theorem prover too weak. 135 trivial. 0 not checked. [2022-07-13 10:12:55,396 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:12:55,396 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1987524925] [2022-07-13 10:12:55,396 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1987524925] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:12:55,396 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [582133758] [2022-07-13 10:12:55,396 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-07-13 10:12:55,397 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:12:55,397 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:12:55,400 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) [2022-07-13 10:12:55,425 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-07-13 10:12:55,554 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-07-13 10:12:55,555 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-13 10:12:55,557 INFO L263 TraceCheckSpWp]: Trace formula consists of 356 conjuncts, 36 conjunts are in the unsatisfiable core [2022-07-13 10:12:55,561 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:12:55,663 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2022-07-13 10:13:03,760 INFO L356 Elim1Store]: treesize reduction 42, result has 22.2 percent of original size [2022-07-13 10:13:03,761 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 29 [2022-07-13 10:13:11,850 INFO L356 Elim1Store]: treesize reduction 42, result has 22.2 percent of original size [2022-07-13 10:13:11,851 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 29 [2022-07-13 10:13:19,926 INFO L356 Elim1Store]: treesize reduction 42, result has 22.2 percent of original size [2022-07-13 10:13:19,926 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 29 [2022-07-13 10:13:28,005 INFO L356 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2022-07-13 10:13:28,005 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 23 [2022-07-13 10:13:28,253 INFO L134 CoverageAnalysis]: Checked inductivity of 204 backedges. 72 proven. 69 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2022-07-13 10:13:28,253 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:13:30,383 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2022-07-13 10:13:30,385 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 32 [2022-07-13 10:13:30,464 INFO L134 CoverageAnalysis]: Checked inductivity of 204 backedges. 0 proven. 69 refuted. 0 times theorem prover too weak. 135 trivial. 0 not checked. [2022-07-13 10:13:30,464 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [582133758] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 10:13:30,464 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 10:13:30,465 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14, 12] total 26 [2022-07-13 10:13:30,465 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2145007627] [2022-07-13 10:13:30,465 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 10:13:30,467 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-07-13 10:13:30,468 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:13:30,468 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-07-13 10:13:30,468 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=547, Unknown=5, NotChecked=0, Total=650 [2022-07-13 10:13:30,468 INFO L87 Difference]: Start difference. First operand 2333 states and 3687 transitions. Second operand has 26 states, 26 states have (on average 4.884615384615385) internal successors, (127), 26 states have internal predecessors, (127), 7 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (24), 7 states have call predecessors, (24), 7 states have call successors, (24) [2022-07-13 10:15:36,285 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:15:36,285 INFO L93 Difference]: Finished difference Result 25313 states and 41091 transitions. [2022-07-13 10:15:36,285 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 100 states. [2022-07-13 10:15:36,286 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 4.884615384615385) internal successors, (127), 26 states have internal predecessors, (127), 7 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (24), 7 states have call predecessors, (24), 7 states have call successors, (24) Word has length 95 [2022-07-13 10:15:36,286 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:15:36,349 INFO L225 Difference]: With dead ends: 25313 [2022-07-13 10:15:36,349 INFO L226 Difference]: Without dead ends: 25311 [2022-07-13 10:15:36,363 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 335 GetRequests, 199 SyntacticMatches, 24 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5741 ImplicationChecksByTransitivity, 152.1s TimeCoverageRelationStatistics Valid=1363, Invalid=11456, Unknown=63, NotChecked=0, Total=12882 [2022-07-13 10:15:36,364 INFO L413 NwaCegarLoop]: 425 mSDtfsCounter, 481 mSDsluCounter, 1999 mSDsCounter, 0 mSdLazyCounter, 5406 mSolverCounterSat, 1228 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 492 SdHoareTripleChecker+Valid, 2424 SdHoareTripleChecker+Invalid, 7436 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1228 IncrementalHoareTripleChecker+Valid, 5406 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 802 IncrementalHoareTripleChecker+Unchecked, 3.0s IncrementalHoareTripleChecker+Time [2022-07-13 10:15:36,365 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [492 Valid, 2424 Invalid, 7436 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1228 Valid, 5406 Invalid, 0 Unknown, 802 Unchecked, 3.0s Time] [2022-07-13 10:15:36,385 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25311 states. [2022-07-13 10:15:37,986 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25311 to 4563. [2022-07-13 10:15:37,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4563 states, 3268 states have (on average 1.464810281517748) internal successors, (4787), 3276 states have internal predecessors, (4787), 1263 states have call successors, (1263), 31 states have call predecessors, (1263), 31 states have return successors, (1263), 1255 states have call predecessors, (1263), 1263 states have call successors, (1263) [2022-07-13 10:15:38,001 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4563 states to 4563 states and 7313 transitions. [2022-07-13 10:15:38,001 INFO L78 Accepts]: Start accepts. Automaton has 4563 states and 7313 transitions. Word has length 95 [2022-07-13 10:15:38,001 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:15:38,001 INFO L495 AbstractCegarLoop]: Abstraction has 4563 states and 7313 transitions. [2022-07-13 10:15:38,002 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 4.884615384615385) internal successors, (127), 26 states have internal predecessors, (127), 7 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (24), 7 states have call predecessors, (24), 7 states have call successors, (24) [2022-07-13 10:15:38,002 INFO L276 IsEmpty]: Start isEmpty. Operand 4563 states and 7313 transitions. [2022-07-13 10:15:38,011 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2022-07-13 10:15:38,012 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:15:38,012 INFO L195 NwaCegarLoop]: trace histogram [10, 10, 6, 5, 5, 5, 2, 2, 2, 2, 2, 2, 2, 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] [2022-07-13 10:15:38,037 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-07-13 10:15:38,237 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 [2022-07-13 10:15:38,237 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:15:38,238 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:15:38,238 INFO L85 PathProgramCache]: Analyzing trace with hash 1891302485, now seen corresponding path program 1 times [2022-07-13 10:15:38,238 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:15:38,238 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [791076538] [2022-07-13 10:15:38,238 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:15:38,238 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:15:38,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:38,434 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:15:38,436 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:38,437 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:15:38,438 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:38,439 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:15:38,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:38,441 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:15:38,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:38,443 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:15:38,443 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:38,444 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2022-07-13 10:15:38,445 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:38,446 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 45 [2022-07-13 10:15:38,447 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:38,448 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2022-07-13 10:15:38,449 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:38,450 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 57 [2022-07-13 10:15:38,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:38,452 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2022-07-13 10:15:38,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:38,454 INFO L134 CoverageAnalysis]: Checked inductivity of 204 backedges. 0 proven. 69 refuted. 0 times theorem prover too weak. 135 trivial. 0 not checked. [2022-07-13 10:15:38,454 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:15:38,455 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [791076538] [2022-07-13 10:15:38,455 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [791076538] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:15:38,455 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [42181970] [2022-07-13 10:15:38,455 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:15:38,455 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:15:38,455 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:15:38,457 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) [2022-07-13 10:15:38,458 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-07-13 10:15:38,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:38,561 INFO L263 TraceCheckSpWp]: Trace formula consists of 357 conjuncts, 33 conjunts are in the unsatisfiable core [2022-07-13 10:15:38,564 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:15:38,708 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2022-07-13 10:15:38,787 INFO L356 Elim1Store]: treesize reduction 42, result has 22.2 percent of original size [2022-07-13 10:15:38,787 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:15:38,856 INFO L356 Elim1Store]: treesize reduction 42, result has 22.2 percent of original size [2022-07-13 10:15:38,857 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:15:38,913 INFO L356 Elim1Store]: treesize reduction 42, result has 22.2 percent of original size [2022-07-13 10:15:38,913 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 28 [2022-07-13 10:15:38,970 INFO L356 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2022-07-13 10:15:38,970 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 23 treesize of output 22 [2022-07-13 10:15:39,193 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 7 [2022-07-13 10:15:39,221 INFO L134 CoverageAnalysis]: Checked inductivity of 204 backedges. 72 proven. 69 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2022-07-13 10:15:39,221 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:15:41,515 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 15 [2022-07-13 10:15:41,527 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 30 [2022-07-13 10:15:41,561 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [42181970] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:15:41,561 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-13 10:15:41,561 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 26 [2022-07-13 10:15:41,562 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [182602570] [2022-07-13 10:15:41,562 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-13 10:15:41,562 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-07-13 10:15:41,562 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:15:41,562 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-07-13 10:15:41,563 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=995, Unknown=1, NotChecked=0, Total=1122 [2022-07-13 10:15:41,563 INFO L87 Difference]: Start difference. First operand 4563 states and 7313 transitions. Second operand has 26 states, 26 states have (on average 4.269230769230769) internal successors, (111), 26 states have internal predecessors, (111), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2022-07-13 10:15:51,332 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 10:15:51,333 INFO L93 Difference]: Finished difference Result 21987 states and 35672 transitions. [2022-07-13 10:15:51,333 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2022-07-13 10:15:51,333 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 4.269230769230769) internal successors, (111), 26 states have internal predecessors, (111), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) Word has length 95 [2022-07-13 10:15:51,333 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-13 10:15:51,377 INFO L225 Difference]: With dead ends: 21987 [2022-07-13 10:15:51,377 INFO L226 Difference]: Without dead ends: 21985 [2022-07-13 10:15:51,387 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 230 GetRequests, 148 SyntacticMatches, 14 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1708 ImplicationChecksByTransitivity, 6.7s TimeCoverageRelationStatistics Valid=530, Invalid=4298, Unknown=2, NotChecked=0, Total=4830 [2022-07-13 10:15:51,388 INFO L413 NwaCegarLoop]: 122 mSDtfsCounter, 349 mSDsluCounter, 830 mSDsCounter, 0 mSdLazyCounter, 1765 mSolverCounterSat, 517 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 368 SdHoareTripleChecker+Valid, 952 SdHoareTripleChecker+Invalid, 2430 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 517 IncrementalHoareTripleChecker+Valid, 1765 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 148 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2022-07-13 10:15:51,388 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [368 Valid, 952 Invalid, 2430 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [517 Valid, 1765 Invalid, 0 Unknown, 148 Unchecked, 1.0s Time] [2022-07-13 10:15:51,403 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21985 states. [2022-07-13 10:15:52,995 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21985 to 4687. [2022-07-13 10:15:52,999 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4687 states, 3372 states have (on average 1.4647093712930013) internal successors, (4939), 3372 states have internal predecessors, (4939), 1279 states have call successors, (1279), 35 states have call predecessors, (1279), 35 states have return successors, (1279), 1279 states have call predecessors, (1279), 1279 states have call successors, (1279) [2022-07-13 10:15:53,007 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4687 states to 4687 states and 7497 transitions. [2022-07-13 10:15:53,008 INFO L78 Accepts]: Start accepts. Automaton has 4687 states and 7497 transitions. Word has length 95 [2022-07-13 10:15:53,008 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-13 10:15:53,008 INFO L495 AbstractCegarLoop]: Abstraction has 4687 states and 7497 transitions. [2022-07-13 10:15:53,008 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 4.269230769230769) internal successors, (111), 26 states have internal predecessors, (111), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2022-07-13 10:15:53,008 INFO L276 IsEmpty]: Start isEmpty. Operand 4687 states and 7497 transitions. [2022-07-13 10:15:53,019 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2022-07-13 10:15:53,019 INFO L187 NwaCegarLoop]: Found error trace [2022-07-13 10:15:53,019 INFO L195 NwaCegarLoop]: trace histogram [10, 10, 7, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 10:15:53,044 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-07-13 10:15:53,235 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 [2022-07-13 10:15:53,235 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-13 10:15:53,236 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 10:15:53,236 INFO L85 PathProgramCache]: Analyzing trace with hash 500947145, now seen corresponding path program 7 times [2022-07-13 10:15:53,236 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 10:15:53,236 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1279455985] [2022-07-13 10:15:53,236 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 10:15:53,236 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 10:15:53,272 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:53,414 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-13 10:15:53,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:53,416 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-13 10:15:53,417 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:53,418 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-13 10:15:53,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:53,420 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2022-07-13 10:15:53,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:53,421 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-07-13 10:15:53,421 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:53,422 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2022-07-13 10:15:53,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:53,424 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 45 [2022-07-13 10:15:53,424 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:53,425 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2022-07-13 10:15:53,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:53,427 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 57 [2022-07-13 10:15:53,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:53,429 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2022-07-13 10:15:53,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:53,432 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 135 trivial. 0 not checked. [2022-07-13 10:15:53,432 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 10:15:53,432 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1279455985] [2022-07-13 10:15:53,432 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1279455985] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 10:15:53,432 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1660890933] [2022-07-13 10:15:53,432 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-07-13 10:15:53,433 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 10:15:53,433 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 10:15:53,434 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) [2022-07-13 10:15:53,435 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-07-13 10:15:53,537 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 10:15:53,539 INFO L263 TraceCheckSpWp]: Trace formula consists of 367 conjuncts, 34 conjunts are in the unsatisfiable core [2022-07-13 10:15:53,542 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 10:15:53,591 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2022-07-13 10:15:53,617 INFO L356 Elim1Store]: treesize reduction 42, result has 22.2 percent of original size [2022-07-13 10:15:53,617 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 29 [2022-07-13 10:15:53,647 INFO L356 Elim1Store]: treesize reduction 42, result has 22.2 percent of original size [2022-07-13 10:15:53,648 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 29 [2022-07-13 10:15:53,672 INFO L356 Elim1Store]: treesize reduction 42, result has 22.2 percent of original size [2022-07-13 10:15:53,672 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 29 [2022-07-13 10:15:53,898 INFO L356 Elim1Store]: treesize reduction 14, result has 17.6 percent of original size [2022-07-13 10:15:53,898 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 46 treesize of output 24 [2022-07-13 10:15:53,918 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 135 trivial. 0 not checked. [2022-07-13 10:15:53,918 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 10:15:54,050 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 15 [2022-07-13 10:15:54,052 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 26 [2022-07-13 10:15:54,112 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 135 trivial. 0 not checked. [2022-07-13 10:15:54,113 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1660890933] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 10:15:54,113 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 10:15:54,113 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13, 13] total 21 [2022-07-13 10:15:54,113 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1412678647] [2022-07-13 10:15:54,113 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 10:15:54,115 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-07-13 10:15:54,115 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 10:15:54,115 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-07-13 10:15:54,115 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=364, Unknown=0, NotChecked=0, Total=420 [2022-07-13 10:15:54,116 INFO L87 Difference]: Start difference. First operand 4687 states and 7497 transitions. Second operand has 21 states, 21 states have (on average 4.714285714285714) internal successors, (99), 21 states have internal predecessors, (99), 4 states have call successors, (13), 1 states have call predecessors, (13), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13)