./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/array-crafted/zero_sum_const3.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 6c24879c 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-crafted/zero_sum_const3.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 4a8466707e2bff30c44c48996d40a42275ef25007ed8ba21de1de20ade9b7ba9 --- Real Ultimate output --- This is Ultimate 0.2.2-?-6c24879 [2022-07-11 22:45:18,534 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-11 22:45:18,536 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-11 22:45:18,583 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-11 22:45:18,584 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-11 22:45:18,584 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-11 22:45:18,585 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-11 22:45:18,586 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-11 22:45:18,587 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-11 22:45:18,588 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-11 22:45:18,588 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-11 22:45:18,589 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-11 22:45:18,590 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-11 22:45:18,592 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-11 22:45:18,593 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-11 22:45:18,595 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-11 22:45:18,595 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-11 22:45:18,596 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-11 22:45:18,597 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-11 22:45:18,598 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-11 22:45:18,598 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-11 22:45:18,599 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-11 22:45:18,600 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-11 22:45:18,600 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-11 22:45:18,601 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-11 22:45:18,603 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-11 22:45:18,603 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-11 22:45:18,603 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-11 22:45:18,603 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-11 22:45:18,604 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-11 22:45:18,604 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-11 22:45:18,605 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-11 22:45:18,605 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-11 22:45:18,605 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-11 22:45:18,606 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-11 22:45:18,607 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-11 22:45:18,607 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-11 22:45:18,607 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-11 22:45:18,608 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-11 22:45:18,608 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-11 22:45:18,609 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-11 22:45:18,610 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-11 22:45:18,611 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2022-07-11 22:45:18,639 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-11 22:45:18,640 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-11 22:45:18,640 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-11 22:45:18,640 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-11 22:45:18,641 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-07-11 22:45:18,641 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-07-11 22:45:18,641 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-11 22:45:18,642 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-11 22:45:18,642 INFO L138 SettingsManager]: * Use SBE=true [2022-07-11 22:45:18,642 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-11 22:45:18,643 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-11 22:45:18,643 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-11 22:45:18,643 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-11 22:45:18,643 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-11 22:45:18,643 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-07-11 22:45:18,643 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-07-11 22:45:18,643 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-07-11 22:45:18,643 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-11 22:45:18,644 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-11 22:45:18,645 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-11 22:45:18,645 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-07-11 22:45:18,645 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-11 22:45:18,645 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-11 22:45:18,645 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-07-11 22:45:18,645 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-11 22:45:18,646 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-11 22:45:18,646 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-07-11 22:45:18,646 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-07-11 22:45:18,646 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-11 22:45:18,646 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-07-11 22:45:18,646 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-07-11 22:45:18,646 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-07-11 22:45:18,647 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-07-11 22:45:18,647 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 -> 4a8466707e2bff30c44c48996d40a42275ef25007ed8ba21de1de20ade9b7ba9 [2022-07-11 22:45:18,826 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-11 22:45:18,840 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-11 22:45:18,841 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-11 22:45:18,843 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-11 22:45:18,843 INFO L275 PluginConnector]: CDTParser initialized [2022-07-11 22:45:18,844 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-crafted/zero_sum_const3.c [2022-07-11 22:45:18,894 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/466b09fe9/bb34f61389a8436b936334a849c021c8/FLAGe8e454353 [2022-07-11 22:45:19,223 INFO L306 CDTParser]: Found 1 translation units. [2022-07-11 22:45:19,224 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-crafted/zero_sum_const3.c [2022-07-11 22:45:19,227 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/466b09fe9/bb34f61389a8436b936334a849c021c8/FLAGe8e454353 [2022-07-11 22:45:19,670 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/466b09fe9/bb34f61389a8436b936334a849c021c8 [2022-07-11 22:45:19,673 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-11 22:45:19,674 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-11 22:45:19,675 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-11 22:45:19,675 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-11 22:45:19,677 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-11 22:45:19,677 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.07 10:45:19" (1/1) ... [2022-07-11 22:45:19,678 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@18e743f1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.07 10:45:19, skipping insertion in model container [2022-07-11 22:45:19,678 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.07 10:45:19" (1/1) ... [2022-07-11 22:45:19,682 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-11 22:45:19,693 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-11 22:45:19,803 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-crafted/zero_sum_const3.c[406,419] [2022-07-11 22:45:19,826 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-11 22:45:19,842 INFO L203 MainTranslator]: Completed pre-run [2022-07-11 22:45:19,852 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-crafted/zero_sum_const3.c[406,419] [2022-07-11 22:45:19,861 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-11 22:45:19,868 INFO L208 MainTranslator]: Completed translation [2022-07-11 22:45:19,869 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.07 10:45:19 WrapperNode [2022-07-11 22:45:19,869 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-11 22:45:19,869 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-11 22:45:19,870 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-11 22:45:19,870 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-11 22:45:19,874 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.07 10:45:19" (1/1) ... [2022-07-11 22:45:19,878 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.07 10:45:19" (1/1) ... [2022-07-11 22:45:19,891 INFO L137 Inliner]: procedures = 16, calls = 16, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 104 [2022-07-11 22:45:19,891 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-11 22:45:19,892 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-11 22:45:19,892 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-11 22:45:19,892 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-11 22:45:19,897 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.07 10:45:19" (1/1) ... [2022-07-11 22:45:19,897 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.07 10:45:19" (1/1) ... [2022-07-11 22:45:19,903 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.07 10:45:19" (1/1) ... [2022-07-11 22:45:19,904 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.07 10:45:19" (1/1) ... [2022-07-11 22:45:19,907 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.07 10:45:19" (1/1) ... [2022-07-11 22:45:19,911 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.07 10:45:19" (1/1) ... [2022-07-11 22:45:19,912 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.07 10:45:19" (1/1) ... [2022-07-11 22:45:19,913 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-11 22:45:19,913 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-11 22:45:19,914 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-11 22:45:19,914 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-11 22:45:19,914 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.07 10:45:19" (1/1) ... [2022-07-11 22:45:19,919 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-11 22:45:19,925 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:45:19,934 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-11 22:45:19,937 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-11 22:45:19,969 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-11 22:45:19,970 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-11 22:45:19,970 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-07-11 22:45:19,970 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2022-07-11 22:45:19,971 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-11 22:45:19,971 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-11 22:45:19,973 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-07-11 22:45:20,016 INFO L234 CfgBuilder]: Building ICFG [2022-07-11 22:45:20,017 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-11 22:45:20,111 INFO L275 CfgBuilder]: Performing block encoding [2022-07-11 22:45:20,115 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-11 22:45:20,115 INFO L299 CfgBuilder]: Removed 7 assume(true) statements. [2022-07-11 22:45:20,116 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.07 10:45:20 BoogieIcfgContainer [2022-07-11 22:45:20,117 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-11 22:45:20,118 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-07-11 22:45:20,118 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-07-11 22:45:20,123 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-07-11 22:45:20,123 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.07 10:45:19" (1/3) ... [2022-07-11 22:45:20,124 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37f8834 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.07 10:45:20, skipping insertion in model container [2022-07-11 22:45:20,124 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.07 10:45:19" (2/3) ... [2022-07-11 22:45:20,124 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37f8834 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.07 10:45:20, skipping insertion in model container [2022-07-11 22:45:20,124 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.07 10:45:20" (3/3) ... [2022-07-11 22:45:20,125 INFO L111 eAbstractionObserver]: Analyzing ICFG zero_sum_const3.c [2022-07-11 22:45:20,134 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-07-11 22:45:20,134 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-07-11 22:45:20,175 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-07-11 22:45:20,179 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@231689c2, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@2c1fb3f7 [2022-07-11 22:45:20,180 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-07-11 22:45:20,182 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 30 states have (on average 1.5666666666666667) internal successors, (47), 31 states have internal predecessors, (47), 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-11 22:45:20,187 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2022-07-11 22:45:20,187 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:45:20,187 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:45:20,188 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:45:20,191 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:45:20,191 INFO L85 PathProgramCache]: Analyzing trace with hash 534528496, now seen corresponding path program 1 times [2022-07-11 22:45:20,196 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:45:20,197 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2010064173] [2022-07-11 22:45:20,197 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:45:20,198 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:45:20,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:45:20,309 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-11 22:45:20,310 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:45:20,311 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2010064173] [2022-07-11 22:45:20,312 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2010064173] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-11 22:45:20,312 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-11 22:45:20,312 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-07-11 22:45:20,313 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [334577750] [2022-07-11 22:45:20,313 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-11 22:45:20,317 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-07-11 22:45:20,318 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:45:20,354 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-07-11 22:45:20,356 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-11 22:45:20,357 INFO L87 Difference]: Start difference. First operand has 32 states, 30 states have (on average 1.5666666666666667) internal successors, (47), 31 states have internal predecessors, (47), 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) Second operand has 2 states, 2 states have (on average 9.5) internal successors, (19), 2 states have internal predecessors, (19), 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-11 22:45:20,373 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:45:20,374 INFO L93 Difference]: Finished difference Result 59 states and 86 transitions. [2022-07-11 22:45:20,375 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-11 22:45:20,376 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 9.5) internal successors, (19), 2 states have internal predecessors, (19), 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 19 [2022-07-11 22:45:20,377 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:45:20,381 INFO L225 Difference]: With dead ends: 59 [2022-07-11 22:45:20,381 INFO L226 Difference]: Without dead ends: 27 [2022-07-11 22:45:20,398 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-11 22:45:20,400 INFO L413 NwaCegarLoop]: 39 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, 39 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-11 22:45:20,404 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-11 22:45:20,414 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-07-11 22:45:20,421 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2022-07-11 22:45:20,422 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 26 states have internal predecessors, (33), 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-11 22:45:20,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 33 transitions. [2022-07-11 22:45:20,424 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 33 transitions. Word has length 19 [2022-07-11 22:45:20,424 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:45:20,424 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 33 transitions. [2022-07-11 22:45:20,425 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 9.5) internal successors, (19), 2 states have internal predecessors, (19), 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-11 22:45:20,425 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 33 transitions. [2022-07-11 22:45:20,425 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2022-07-11 22:45:20,426 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:45:20,426 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:45:20,426 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-07-11 22:45:20,426 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:45:20,427 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:45:20,428 INFO L85 PathProgramCache]: Analyzing trace with hash -697412484, now seen corresponding path program 1 times [2022-07-11 22:45:20,428 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:45:20,428 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1593804763] [2022-07-11 22:45:20,429 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:45:20,429 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:45:20,443 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:45:20,494 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-11 22:45:20,494 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:45:20,494 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1593804763] [2022-07-11 22:45:20,495 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1593804763] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-11 22:45:20,495 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-11 22:45:20,495 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-07-11 22:45:20,496 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1000966059] [2022-07-11 22:45:20,496 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-11 22:45:20,498 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-07-11 22:45:20,498 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:45:20,498 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-07-11 22:45:20,498 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-07-11 22:45:20,499 INFO L87 Difference]: Start difference. First operand 27 states and 33 transitions. Second operand has 3 states, 3 states have (on average 6.333333333333333) internal successors, (19), 3 states have internal predecessors, (19), 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-11 22:45:20,558 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:45:20,558 INFO L93 Difference]: Finished difference Result 51 states and 63 transitions. [2022-07-11 22:45:20,559 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-07-11 22:45:20,560 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 6.333333333333333) internal successors, (19), 3 states have internal predecessors, (19), 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 19 [2022-07-11 22:45:20,560 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:45:20,560 INFO L225 Difference]: With dead ends: 51 [2022-07-11 22:45:20,560 INFO L226 Difference]: Without dead ends: 29 [2022-07-11 22:45:20,563 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-07-11 22:45:20,564 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 1 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-11 22:45:20,565 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 34 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-11 22:45:20,566 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2022-07-11 22:45:20,572 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 28. [2022-07-11 22:45:20,572 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 27 states have internal predecessors, (34), 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-11 22:45:20,573 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 34 transitions. [2022-07-11 22:45:20,573 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 34 transitions. Word has length 19 [2022-07-11 22:45:20,573 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:45:20,574 INFO L495 AbstractCegarLoop]: Abstraction has 28 states and 34 transitions. [2022-07-11 22:45:20,575 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 6.333333333333333) internal successors, (19), 3 states have internal predecessors, (19), 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-11 22:45:20,575 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 34 transitions. [2022-07-11 22:45:20,577 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-07-11 22:45:20,577 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:45:20,577 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:45:20,578 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-07-11 22:45:20,578 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:45:20,579 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:45:20,580 INFO L85 PathProgramCache]: Analyzing trace with hash -506383970, now seen corresponding path program 1 times [2022-07-11 22:45:20,580 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:45:20,581 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1824387207] [2022-07-11 22:45:20,581 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:45:20,581 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:45:20,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:45:20,630 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-07-11 22:45:20,633 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:45:20,633 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1824387207] [2022-07-11 22:45:20,633 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1824387207] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-11 22:45:20,634 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-11 22:45:20,634 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-07-11 22:45:20,634 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [24573432] [2022-07-11 22:45:20,634 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-11 22:45:20,635 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-07-11 22:45:20,635 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:45:20,635 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-07-11 22:45:20,635 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2022-07-11 22:45:20,636 INFO L87 Difference]: Start difference. First operand 28 states and 34 transitions. Second operand has 4 states, 4 states have (on average 5.25) internal successors, (21), 4 states have internal predecessors, (21), 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-11 22:45:20,709 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:45:20,709 INFO L93 Difference]: Finished difference Result 60 states and 76 transitions. [2022-07-11 22:45:20,710 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-07-11 22:45:20,710 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 5.25) internal successors, (21), 4 states have internal predecessors, (21), 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 21 [2022-07-11 22:45:20,710 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:45:20,711 INFO L225 Difference]: With dead ends: 60 [2022-07-11 22:45:20,711 INFO L226 Difference]: Without dead ends: 41 [2022-07-11 22:45:20,713 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2022-07-11 22:45:20,715 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 40 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 15 SdHoareTripleChecker+Invalid, 61 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-11 22:45:20,716 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 15 Invalid, 61 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-11 22:45:20,717 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-07-11 22:45:20,720 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 34. [2022-07-11 22:45:20,721 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 33 states have (on average 1.2121212121212122) internal successors, (40), 33 states have internal predecessors, (40), 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-11 22:45:20,721 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 40 transitions. [2022-07-11 22:45:20,721 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 40 transitions. Word has length 21 [2022-07-11 22:45:20,721 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:45:20,721 INFO L495 AbstractCegarLoop]: Abstraction has 34 states and 40 transitions. [2022-07-11 22:45:20,722 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 5.25) internal successors, (21), 4 states have internal predecessors, (21), 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-11 22:45:20,722 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 40 transitions. [2022-07-11 22:45:20,722 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-07-11 22:45:20,722 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:45:20,722 INFO L195 NwaCegarLoop]: trace histogram [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-11 22:45:20,722 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-07-11 22:45:20,722 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:45:20,723 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:45:20,723 INFO L85 PathProgramCache]: Analyzing trace with hash 615846698, now seen corresponding path program 1 times [2022-07-11 22:45:20,723 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:45:20,723 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [16512641] [2022-07-11 22:45:20,723 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:45:20,723 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:45:20,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:45:20,777 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-11 22:45:20,778 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:45:20,778 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [16512641] [2022-07-11 22:45:20,778 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [16512641] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:45:20,778 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1242702438] [2022-07-11 22:45:20,778 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:45:20,778 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:45:20,779 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:45:20,780 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-11 22:45:20,781 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-11 22:45:20,832 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:45:20,833 INFO L263 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 4 conjunts are in the unsatisfiable core [2022-07-11 22:45:20,836 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:45:20,894 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-11 22:45:20,894 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:45:20,915 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-11 22:45:20,915 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1242702438] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:45:20,916 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:45:20,916 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 7 [2022-07-11 22:45:20,916 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [602131461] [2022-07-11 22:45:20,916 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:45:20,917 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-11 22:45:20,917 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:45:20,917 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-11 22:45:20,917 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2022-07-11 22:45:20,917 INFO L87 Difference]: Start difference. First operand 34 states and 40 transitions. Second operand has 7 states, 7 states have (on average 5.714285714285714) internal successors, (40), 7 states have internal predecessors, (40), 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-11 22:45:20,965 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:45:20,965 INFO L93 Difference]: Finished difference Result 65 states and 77 transitions. [2022-07-11 22:45:20,965 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-11 22:45:20,965 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 5.714285714285714) internal successors, (40), 7 states have internal predecessors, (40), 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 33 [2022-07-11 22:45:20,966 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:45:20,966 INFO L225 Difference]: With dead ends: 65 [2022-07-11 22:45:20,966 INFO L226 Difference]: Without dead ends: 37 [2022-07-11 22:45:20,966 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 62 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2022-07-11 22:45:20,967 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 2 mSDsluCounter, 9 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 96 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-11 22:45:20,967 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 34 Invalid, 96 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-11 22:45:20,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2022-07-11 22:45:20,970 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 36. [2022-07-11 22:45:20,970 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 35 states have (on average 1.2) internal successors, (42), 35 states have internal predecessors, (42), 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-11 22:45:20,971 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 42 transitions. [2022-07-11 22:45:20,971 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 42 transitions. Word has length 33 [2022-07-11 22:45:20,971 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:45:20,971 INFO L495 AbstractCegarLoop]: Abstraction has 36 states and 42 transitions. [2022-07-11 22:45:20,971 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 5.714285714285714) internal successors, (40), 7 states have internal predecessors, (40), 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-11 22:45:20,972 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 42 transitions. [2022-07-11 22:45:20,972 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2022-07-11 22:45:20,972 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:45:20,972 INFO L195 NwaCegarLoop]: trace histogram [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] [2022-07-11 22:45:20,988 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-07-11 22:45:21,184 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:45:21,184 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:45:21,184 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:45:21,185 INFO L85 PathProgramCache]: Analyzing trace with hash -160084788, now seen corresponding path program 2 times [2022-07-11 22:45:21,185 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:45:21,185 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2039689423] [2022-07-11 22:45:21,185 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:45:21,185 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:45:21,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:45:21,248 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-07-11 22:45:21,249 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:45:21,249 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2039689423] [2022-07-11 22:45:21,249 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2039689423] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:45:21,249 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1158770518] [2022-07-11 22:45:21,249 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-11 22:45:21,249 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:45:21,250 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:45:21,251 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-11 22:45:21,252 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-11 22:45:21,298 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-11 22:45:21,299 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:45:21,300 INFO L263 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 4 conjunts are in the unsatisfiable core [2022-07-11 22:45:21,304 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:45:21,341 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-07-11 22:45:21,341 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:45:21,365 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-07-11 22:45:21,365 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1158770518] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:45:21,365 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:45:21,365 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 8 [2022-07-11 22:45:21,366 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [433878913] [2022-07-11 22:45:21,366 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:45:21,366 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-07-11 22:45:21,366 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:45:21,366 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-07-11 22:45:21,367 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=31, Unknown=0, NotChecked=0, Total=56 [2022-07-11 22:45:21,367 INFO L87 Difference]: Start difference. First operand 36 states and 42 transitions. Second operand has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 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-11 22:45:21,448 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:45:21,448 INFO L93 Difference]: Finished difference Result 79 states and 95 transitions. [2022-07-11 22:45:21,449 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-11 22:45:21,449 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 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 35 [2022-07-11 22:45:21,449 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:45:21,449 INFO L225 Difference]: With dead ends: 79 [2022-07-11 22:45:21,450 INFO L226 Difference]: Without dead ends: 55 [2022-07-11 22:45:21,450 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 65 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=32, Invalid=40, Unknown=0, NotChecked=0, Total=72 [2022-07-11 22:45:21,451 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 49 mSDsluCounter, 6 mSDsCounter, 0 mSdLazyCounter, 69 mSolverCounterSat, 57 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 18 SdHoareTripleChecker+Invalid, 126 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 57 IncrementalHoareTripleChecker+Valid, 69 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-11 22:45:21,451 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 18 Invalid, 126 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [57 Valid, 69 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-11 22:45:21,451 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-07-11 22:45:21,454 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 48. [2022-07-11 22:45:21,454 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 47 states have (on average 1.148936170212766) internal successors, (54), 47 states have internal predecessors, (54), 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-11 22:45:21,455 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 54 transitions. [2022-07-11 22:45:21,455 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 54 transitions. Word has length 35 [2022-07-11 22:45:21,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:45:21,455 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 54 transitions. [2022-07-11 22:45:21,455 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 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-11 22:45:21,455 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 54 transitions. [2022-07-11 22:45:21,456 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-07-11 22:45:21,456 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:45:21,456 INFO L195 NwaCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1] [2022-07-11 22:45:21,474 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-11 22:45:21,674 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:45:21,675 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:45:21,675 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:45:21,675 INFO L85 PathProgramCache]: Analyzing trace with hash -1337652904, now seen corresponding path program 3 times [2022-07-11 22:45:21,675 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:45:21,675 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [56646536] [2022-07-11 22:45:21,675 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:45:21,675 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:45:21,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:45:22,471 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-11 22:45:22,471 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:45:22,471 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [56646536] [2022-07-11 22:45:22,472 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [56646536] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:45:22,472 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1893138478] [2022-07-11 22:45:22,472 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-11 22:45:22,472 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:45:22,472 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:45:22,473 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-11 22:45:22,474 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-11 22:45:22,525 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-07-11 22:45:22,526 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:45:22,527 INFO L263 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 66 conjunts are in the unsatisfiable core [2022-07-11 22:45:22,531 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:45:23,499 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-11 22:45:23,500 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 17 treesize of output 18 [2022-07-11 22:45:23,666 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-11 22:45:23,666 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:45:26,317 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-11 22:45:26,318 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 37 treesize of output 94 [2022-07-11 22:45:26,802 INFO L356 Elim1Store]: treesize reduction 76, result has 10.6 percent of original size [2022-07-11 22:45:26,802 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 36 treesize of output 17 [2022-07-11 22:45:27,237 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-11 22:45:27,237 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1893138478] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:45:27,237 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:45:27,237 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 21, 26] total 58 [2022-07-11 22:45:27,237 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1098573114] [2022-07-11 22:45:27,238 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:45:27,238 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 58 states [2022-07-11 22:45:27,238 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:45:27,238 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 58 interpolants. [2022-07-11 22:45:27,239 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=354, Invalid=2952, Unknown=0, NotChecked=0, Total=3306 [2022-07-11 22:45:27,240 INFO L87 Difference]: Start difference. First operand 48 states and 54 transitions. Second operand has 58 states, 58 states have (on average 2.293103448275862) internal successors, (133), 58 states have internal predecessors, (133), 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-11 22:45:29,100 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:45:29,100 INFO L93 Difference]: Finished difference Result 132 states and 152 transitions. [2022-07-11 22:45:29,100 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2022-07-11 22:45:29,101 INFO L78 Accepts]: Start accepts. Automaton has has 58 states, 58 states have (on average 2.293103448275862) internal successors, (133), 58 states have internal predecessors, (133), 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 47 [2022-07-11 22:45:29,101 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:45:29,102 INFO L225 Difference]: With dead ends: 132 [2022-07-11 22:45:29,103 INFO L226 Difference]: Without dead ends: 126 [2022-07-11 22:45:29,105 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 51 SyntacticMatches, 27 SemanticMatches, 82 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2290 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=788, Invalid=6184, Unknown=0, NotChecked=0, Total=6972 [2022-07-11 22:45:29,105 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 35 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 328 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 949 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 328 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 599 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-11 22:45:29,105 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 93 Invalid, 949 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 328 Invalid, 0 Unknown, 599 Unchecked, 0.2s Time] [2022-07-11 22:45:29,106 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2022-07-11 22:45:29,115 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 87. [2022-07-11 22:45:29,115 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 86 states have (on average 1.1744186046511629) internal successors, (101), 86 states have internal predecessors, (101), 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-11 22:45:29,116 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 101 transitions. [2022-07-11 22:45:29,116 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 101 transitions. Word has length 47 [2022-07-11 22:45:29,116 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:45:29,116 INFO L495 AbstractCegarLoop]: Abstraction has 87 states and 101 transitions. [2022-07-11 22:45:29,116 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 58 states, 58 states have (on average 2.293103448275862) internal successors, (133), 58 states have internal predecessors, (133), 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-11 22:45:29,116 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 101 transitions. [2022-07-11 22:45:29,117 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2022-07-11 22:45:29,117 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:45:29,117 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:45:29,133 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-11 22:45:29,323 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:45:29,323 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:45:29,324 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:45:29,324 INFO L85 PathProgramCache]: Analyzing trace with hash -1235984134, now seen corresponding path program 4 times [2022-07-11 22:45:29,324 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:45:29,324 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1837460354] [2022-07-11 22:45:29,324 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:45:29,324 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:45:29,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:45:29,390 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2022-07-11 22:45:29,391 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:45:29,391 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1837460354] [2022-07-11 22:45:29,391 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1837460354] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:45:29,391 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1246926258] [2022-07-11 22:45:29,391 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-11 22:45:29,391 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:45:29,391 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:45:29,392 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-11 22:45:29,394 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-11 22:45:29,429 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-11 22:45:29,429 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:45:29,430 INFO L263 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 8 conjunts are in the unsatisfiable core [2022-07-11 22:45:29,431 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:45:29,494 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 9 proven. 4 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2022-07-11 22:45:29,495 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:45:29,545 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 9 proven. 4 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2022-07-11 22:45:29,546 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1246926258] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:45:29,546 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:45:29,546 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2022-07-11 22:45:29,546 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1821945530] [2022-07-11 22:45:29,546 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:45:29,547 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-07-11 22:45:29,547 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:45:29,548 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-07-11 22:45:29,548 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=129, Unknown=0, NotChecked=0, Total=182 [2022-07-11 22:45:29,548 INFO L87 Difference]: Start difference. First operand 87 states and 101 transitions. Second operand has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 14 states have internal predecessors, (51), 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-11 22:45:29,745 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:45:29,746 INFO L93 Difference]: Finished difference Result 193 states and 222 transitions. [2022-07-11 22:45:29,746 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-07-11 22:45:29,746 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 14 states have internal predecessors, (51), 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 49 [2022-07-11 22:45:29,747 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:45:29,747 INFO L225 Difference]: With dead ends: 193 [2022-07-11 22:45:29,747 INFO L226 Difference]: Without dead ends: 120 [2022-07-11 22:45:29,748 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 92 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=80, Invalid=192, Unknown=0, NotChecked=0, Total=272 [2022-07-11 22:45:29,748 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 161 mSDsluCounter, 20 mSDsCounter, 0 mSdLazyCounter, 180 mSolverCounterSat, 178 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 161 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 358 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 178 IncrementalHoareTripleChecker+Valid, 180 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-11 22:45:29,748 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [161 Valid, 32 Invalid, 358 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [178 Valid, 180 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-11 22:45:29,749 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2022-07-11 22:45:29,755 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 100. [2022-07-11 22:45:29,755 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 99 states have (on average 1.1414141414141414) internal successors, (113), 99 states have internal predecessors, (113), 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-11 22:45:29,756 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 113 transitions. [2022-07-11 22:45:29,756 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 113 transitions. Word has length 49 [2022-07-11 22:45:29,756 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:45:29,756 INFO L495 AbstractCegarLoop]: Abstraction has 100 states and 113 transitions. [2022-07-11 22:45:29,756 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 14 states have internal predecessors, (51), 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-11 22:45:29,756 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 113 transitions. [2022-07-11 22:45:29,757 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-07-11 22:45:29,757 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:45:29,757 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:45:29,779 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-07-11 22:45:29,971 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:45:29,971 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:45:29,972 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:45:29,972 INFO L85 PathProgramCache]: Analyzing trace with hash -925733540, now seen corresponding path program 5 times [2022-07-11 22:45:29,972 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:45:29,972 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [551529835] [2022-07-11 22:45:29,972 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:45:29,972 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:45:29,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:45:30,036 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 1 proven. 12 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2022-07-11 22:45:30,036 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:45:30,036 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [551529835] [2022-07-11 22:45:30,037 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [551529835] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:45:30,037 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1764166317] [2022-07-11 22:45:30,037 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-11 22:45:30,037 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:45:30,037 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:45:30,038 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-11 22:45:30,039 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-11 22:45:30,092 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2022-07-11 22:45:30,092 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:45:30,093 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 8 conjunts are in the unsatisfiable core [2022-07-11 22:45:30,094 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:45:30,146 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 4 proven. 9 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2022-07-11 22:45:30,146 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:45:30,187 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 4 proven. 9 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2022-07-11 22:45:30,187 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1764166317] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:45:30,187 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:45:30,187 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2022-07-11 22:45:30,188 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1344414055] [2022-07-11 22:45:30,188 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:45:30,188 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-07-11 22:45:30,188 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:45:30,189 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-07-11 22:45:30,189 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=129, Unknown=0, NotChecked=0, Total=182 [2022-07-11 22:45:30,189 INFO L87 Difference]: Start difference. First operand 100 states and 113 transitions. Second operand has 14 states, 14 states have (on average 4.428571428571429) internal successors, (62), 14 states have internal predecessors, (62), 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-11 22:45:30,357 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:45:30,358 INFO L93 Difference]: Finished difference Result 112 states and 125 transitions. [2022-07-11 22:45:30,358 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-07-11 22:45:30,358 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.428571428571429) internal successors, (62), 14 states have internal predecessors, (62), 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 51 [2022-07-11 22:45:30,358 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:45:30,358 INFO L225 Difference]: With dead ends: 112 [2022-07-11 22:45:30,359 INFO L226 Difference]: Without dead ends: 78 [2022-07-11 22:45:30,359 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 95 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 84 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=101, Invalid=279, Unknown=0, NotChecked=0, Total=380 [2022-07-11 22:45:30,359 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 127 mSDsluCounter, 11 mSDsCounter, 0 mSdLazyCounter, 232 mSolverCounterSat, 116 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 127 SdHoareTripleChecker+Valid, 23 SdHoareTripleChecker+Invalid, 348 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 116 IncrementalHoareTripleChecker+Valid, 232 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-11 22:45:30,360 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [127 Valid, 23 Invalid, 348 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [116 Valid, 232 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-11 22:45:30,360 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2022-07-11 22:45:30,364 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 62. [2022-07-11 22:45:30,364 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 61 states have (on average 1.1147540983606556) internal successors, (68), 61 states have internal predecessors, (68), 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-11 22:45:30,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 68 transitions. [2022-07-11 22:45:30,364 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 68 transitions. Word has length 51 [2022-07-11 22:45:30,364 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:45:30,365 INFO L495 AbstractCegarLoop]: Abstraction has 62 states and 68 transitions. [2022-07-11 22:45:30,365 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.428571428571429) internal successors, (62), 14 states have internal predecessors, (62), 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-11 22:45:30,365 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 68 transitions. [2022-07-11 22:45:30,365 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2022-07-11 22:45:30,365 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:45:30,366 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:45:30,381 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-11 22:45:30,579 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:45:30,579 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:45:30,580 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:45:30,580 INFO L85 PathProgramCache]: Analyzing trace with hash -1781065978, now seen corresponding path program 6 times [2022-07-11 22:45:30,580 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:45:30,580 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1928645384] [2022-07-11 22:45:30,580 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:45:30,580 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:45:30,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:45:32,842 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 0 proven. 63 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-11 22:45:32,842 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:45:32,842 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1928645384] [2022-07-11 22:45:32,842 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1928645384] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:45:32,842 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [177795676] [2022-07-11 22:45:32,842 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-07-11 22:45:32,843 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:45:32,843 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:45:32,844 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-11 22:45:32,844 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-11 22:45:32,889 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-07-11 22:45:32,890 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:45:32,891 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 88 conjunts are in the unsatisfiable core [2022-07-11 22:45:32,893 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:45:35,723 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:45:35,724 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-11 22:45:35,724 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-11 22:45:35,725 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:45:35,725 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:45:35,726 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-11 22:45:35,726 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-11 22:45:35,735 INFO L356 Elim1Store]: treesize reduction 6, result has 68.4 percent of original size [2022-07-11 22:45:35,735 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 1 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 55 treesize of output 28 [2022-07-11 22:45:35,826 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 0 proven. 63 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-11 22:45:35,826 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:46:31,462 INFO L356 Elim1Store]: treesize reduction 185, result has 55.3 percent of original size [2022-07-11 22:46:31,463 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 8 select indices, 8 select index equivalence classes, 0 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 75 treesize of output 245 [2022-07-11 22:46:32,981 INFO L356 Elim1Store]: treesize reduction 393, result has 5.1 percent of original size [2022-07-11 22:46:32,981 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 8 select indices, 8 select index equivalence classes, 0 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 76 treesize of output 38 [2022-07-11 22:46:33,439 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 4 proven. 59 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-11 22:46:33,440 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [177795676] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:46:33,440 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:46:33,440 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [46, 44, 40] total 121 [2022-07-11 22:46:33,440 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [191326378] [2022-07-11 22:46:33,440 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:46:33,440 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 121 states [2022-07-11 22:46:33,440 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:46:33,441 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 121 interpolants. [2022-07-11 22:46:33,444 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=931, Invalid=13575, Unknown=14, NotChecked=0, Total=14520 [2022-07-11 22:46:33,444 INFO L87 Difference]: Start difference. First operand 62 states and 68 transitions. Second operand has 121 states, 121 states have (on average 1.3884297520661157) internal successors, (168), 121 states have internal predecessors, (168), 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-11 22:46:39,094 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:46:39,095 INFO L93 Difference]: Finished difference Result 114 states and 126 transitions. [2022-07-11 22:46:39,095 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2022-07-11 22:46:39,095 INFO L78 Accepts]: Start accepts. Automaton has has 121 states, 121 states have (on average 1.3884297520661157) internal successors, (168), 121 states have internal predecessors, (168), 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 61 [2022-07-11 22:46:39,096 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:46:39,096 INFO L225 Difference]: With dead ends: 114 [2022-07-11 22:46:39,096 INFO L226 Difference]: Without dead ends: 110 [2022-07-11 22:46:39,101 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 224 GetRequests, 43 SyntacticMatches, 13 SemanticMatches, 168 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8989 ImplicationChecksByTransitivity, 63.9s TimeCoverageRelationStatistics Valid=1930, Invalid=26786, Unknown=14, NotChecked=0, Total=28730 [2022-07-11 22:46:39,101 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 39 mSDsluCounter, 147 mSDsCounter, 0 mSdLazyCounter, 1347 mSolverCounterSat, 196 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 2925 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 196 IncrementalHoareTripleChecker+Valid, 1347 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 1382 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-07-11 22:46:39,101 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 160 Invalid, 2925 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [196 Valid, 1347 Invalid, 0 Unknown, 1382 Unchecked, 0.8s Time] [2022-07-11 22:46:39,102 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2022-07-11 22:46:39,109 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 99. [2022-07-11 22:46:39,109 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 98 states have (on average 1.1224489795918366) internal successors, (110), 98 states have internal predecessors, (110), 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-11 22:46:39,110 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 110 transitions. [2022-07-11 22:46:39,110 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 110 transitions. Word has length 61 [2022-07-11 22:46:39,110 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:46:39,110 INFO L495 AbstractCegarLoop]: Abstraction has 99 states and 110 transitions. [2022-07-11 22:46:39,110 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 121 states, 121 states have (on average 1.3884297520661157) internal successors, (168), 121 states have internal predecessors, (168), 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-11 22:46:39,110 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 110 transitions. [2022-07-11 22:46:39,111 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2022-07-11 22:46:39,111 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:46:39,111 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:46:39,128 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-11 22:46:39,327 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:46:39,328 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:46:39,328 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:46:39,328 INFO L85 PathProgramCache]: Analyzing trace with hash 2140781352, now seen corresponding path program 7 times [2022-07-11 22:46:39,328 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:46:39,328 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1497772373] [2022-07-11 22:46:39,328 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:46:39,328 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:46:39,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:46:39,403 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 11 proven. 14 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-07-11 22:46:39,404 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:46:39,404 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1497772373] [2022-07-11 22:46:39,404 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1497772373] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:46:39,404 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [332555708] [2022-07-11 22:46:39,404 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-07-11 22:46:39,404 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:46:39,405 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:46:39,420 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-11 22:46:39,421 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-11 22:46:39,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:46:39,467 INFO L263 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 10 conjunts are in the unsatisfiable core [2022-07-11 22:46:39,469 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:46:39,559 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-07-11 22:46:39,560 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:46:39,631 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-07-11 22:46:39,631 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [332555708] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:46:39,631 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:46:39,631 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2022-07-11 22:46:39,633 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [390673604] [2022-07-11 22:46:39,633 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:46:39,634 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-07-11 22:46:39,634 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:46:39,634 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-07-11 22:46:39,634 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=197, Unknown=0, NotChecked=0, Total=272 [2022-07-11 22:46:39,634 INFO L87 Difference]: Start difference. First operand 99 states and 110 transitions. Second operand has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 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-11 22:46:39,877 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:46:39,877 INFO L93 Difference]: Finished difference Result 221 states and 246 transitions. [2022-07-11 22:46:39,877 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-07-11 22:46:39,878 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 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 63 [2022-07-11 22:46:39,878 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:46:39,878 INFO L225 Difference]: With dead ends: 221 [2022-07-11 22:46:39,878 INFO L226 Difference]: Without dead ends: 126 [2022-07-11 22:46:39,879 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 119 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 107 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=117, Invalid=303, Unknown=0, NotChecked=0, Total=420 [2022-07-11 22:46:39,879 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 138 mSDsluCounter, 30 mSDsCounter, 0 mSdLazyCounter, 399 mSolverCounterSat, 131 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 138 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 530 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 131 IncrementalHoareTripleChecker+Valid, 399 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-11 22:46:39,880 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [138 Valid, 42 Invalid, 530 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [131 Valid, 399 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-11 22:46:39,880 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2022-07-11 22:46:39,886 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 106. [2022-07-11 22:46:39,886 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 105 states have (on average 1.1047619047619048) internal successors, (116), 105 states have internal predecessors, (116), 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-11 22:46:39,886 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 116 transitions. [2022-07-11 22:46:39,886 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 116 transitions. Word has length 63 [2022-07-11 22:46:39,887 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:46:39,887 INFO L495 AbstractCegarLoop]: Abstraction has 106 states and 116 transitions. [2022-07-11 22:46:39,887 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 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-11 22:46:39,887 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 116 transitions. [2022-07-11 22:46:39,887 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2022-07-11 22:46:39,888 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:46:39,888 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:46:39,904 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-11 22:46:40,095 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:46:40,095 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:46:40,096 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:46:40,096 INFO L85 PathProgramCache]: Analyzing trace with hash 156775434, now seen corresponding path program 8 times [2022-07-11 22:46:40,096 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:46:40,096 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2121956311] [2022-07-11 22:46:40,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:46:40,096 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:46:40,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:46:40,168 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 4 proven. 21 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-07-11 22:46:40,169 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:46:40,169 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2121956311] [2022-07-11 22:46:40,169 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2121956311] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:46:40,169 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1105170890] [2022-07-11 22:46:40,169 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-11 22:46:40,169 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:46:40,170 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:46:40,171 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-11 22:46:40,172 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-11 22:46:40,222 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-11 22:46:40,222 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:46:40,223 INFO L263 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 10 conjunts are in the unsatisfiable core [2022-07-11 22:46:40,224 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:46:40,295 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 9 proven. 16 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-07-11 22:46:40,296 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:46:40,337 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 9 proven. 16 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-07-11 22:46:40,338 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1105170890] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:46:40,338 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:46:40,338 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2022-07-11 22:46:40,338 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1686165884] [2022-07-11 22:46:40,338 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:46:40,338 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-07-11 22:46:40,338 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:46:40,339 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-07-11 22:46:40,339 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=197, Unknown=0, NotChecked=0, Total=272 [2022-07-11 22:46:40,340 INFO L87 Difference]: Start difference. First operand 106 states and 116 transitions. Second operand has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 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-11 22:46:40,560 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:46:40,560 INFO L93 Difference]: Finished difference Result 118 states and 128 transitions. [2022-07-11 22:46:40,561 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-07-11 22:46:40,561 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 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 65 [2022-07-11 22:46:40,561 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:46:40,561 INFO L225 Difference]: With dead ends: 118 [2022-07-11 22:46:40,561 INFO L226 Difference]: Without dead ends: 82 [2022-07-11 22:46:40,562 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 147 GetRequests, 122 SyntacticMatches, 2 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 148 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=149, Invalid=451, Unknown=0, NotChecked=0, Total=600 [2022-07-11 22:46:40,562 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 149 mSDsluCounter, 8 mSDsCounter, 0 mSdLazyCounter, 324 mSolverCounterSat, 149 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 149 SdHoareTripleChecker+Valid, 20 SdHoareTripleChecker+Invalid, 473 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 149 IncrementalHoareTripleChecker+Valid, 324 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-11 22:46:40,562 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [149 Valid, 20 Invalid, 473 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [149 Valid, 324 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-11 22:46:40,563 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2022-07-11 22:46:40,567 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 76. [2022-07-11 22:46:40,567 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 76 states, 75 states have (on average 1.0933333333333333) internal successors, (82), 75 states have internal predecessors, (82), 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-11 22:46:40,567 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 82 transitions. [2022-07-11 22:46:40,568 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 82 transitions. Word has length 65 [2022-07-11 22:46:40,568 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:46:40,568 INFO L495 AbstractCegarLoop]: Abstraction has 76 states and 82 transitions. [2022-07-11 22:46:40,568 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 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-11 22:46:40,568 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 82 transitions. [2022-07-11 22:46:40,569 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-07-11 22:46:40,569 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:46:40,569 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:46:40,587 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-11 22:46:40,781 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,SelfDestructingSolverStorable10 [2022-07-11 22:46:40,782 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:46:40,782 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:46:40,782 INFO L85 PathProgramCache]: Analyzing trace with hash 958143540, now seen corresponding path program 9 times [2022-07-11 22:46:40,782 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:46:40,782 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1743500214] [2022-07-11 22:46:40,782 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:46:40,782 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:46:40,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:46:44,513 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 0 proven. 112 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-11 22:46:44,513 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:46:44,513 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1743500214] [2022-07-11 22:46:44,513 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1743500214] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:46:44,513 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1888222294] [2022-07-11 22:46:44,514 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-11 22:46:44,514 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:46:44,514 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:46:44,515 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-11 22:46:44,515 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-11 22:46:44,571 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2022-07-11 22:46:44,571 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:46:44,573 WARN L261 TraceCheckSpWp]: Trace formula consists of 223 conjuncts, 120 conjunts are in the unsatisfiable core [2022-07-11 22:46:44,576 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:46:44,652 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 15 treesize of output 11 [2022-07-11 22:46:51,727 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:46:51,727 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:46:51,729 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:46:51,738 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-11 22:46:51,739 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 38 treesize of output 53 [2022-07-11 22:46:52,004 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 5 proven. 103 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-11 22:46:52,004 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:46:58,094 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 0 proven. 103 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-07-11 22:46:58,095 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1888222294] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:46:58,095 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:46:58,095 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 26, 21] total 103 [2022-07-11 22:46:58,095 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1410232002] [2022-07-11 22:46:58,095 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:46:58,095 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 103 states [2022-07-11 22:46:58,095 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:46:58,096 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 103 interpolants. [2022-07-11 22:46:58,098 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=527, Invalid=9979, Unknown=0, NotChecked=0, Total=10506 [2022-07-11 22:46:58,098 INFO L87 Difference]: Start difference. First operand 76 states and 82 transitions. Second operand has 103 states, 103 states have (on average 2.029126213592233) internal successors, (209), 103 states have internal predecessors, (209), 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-11 22:47:09,258 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:47:09,258 INFO L93 Difference]: Finished difference Result 146 states and 159 transitions. [2022-07-11 22:47:09,258 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 98 states. [2022-07-11 22:47:09,258 INFO L78 Accepts]: Start accepts. Automaton has has 103 states, 103 states have (on average 2.029126213592233) internal successors, (209), 103 states have internal predecessors, (209), 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 75 [2022-07-11 22:47:09,259 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:47:09,259 INFO L225 Difference]: With dead ends: 146 [2022-07-11 22:47:09,259 INFO L226 Difference]: Without dead ends: 142 [2022-07-11 22:47:09,261 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 298 GetRequests, 86 SyntacticMatches, 29 SemanticMatches, 183 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 8928 ImplicationChecksByTransitivity, 24.7s TimeCoverageRelationStatistics Valid=1834, Invalid=32206, Unknown=0, NotChecked=0, Total=34040 [2022-07-11 22:47:09,261 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 36 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 1388 mSolverCounterSat, 263 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 2542 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 263 IncrementalHoareTripleChecker+Valid, 1388 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 891 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-07-11 22:47:09,262 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 163 Invalid, 2542 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [263 Valid, 1388 Invalid, 0 Unknown, 891 Unchecked, 0.8s Time] [2022-07-11 22:47:09,262 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2022-07-11 22:47:09,275 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 111. [2022-07-11 22:47:09,275 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 110 states have (on average 1.1) internal successors, (121), 110 states have internal predecessors, (121), 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-11 22:47:09,276 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 121 transitions. [2022-07-11 22:47:09,276 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 121 transitions. Word has length 75 [2022-07-11 22:47:09,276 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:47:09,276 INFO L495 AbstractCegarLoop]: Abstraction has 111 states and 121 transitions. [2022-07-11 22:47:09,276 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 103 states, 103 states have (on average 2.029126213592233) internal successors, (209), 103 states have internal predecessors, (209), 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-11 22:47:09,276 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 121 transitions. [2022-07-11 22:47:09,277 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2022-07-11 22:47:09,277 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:47:09,277 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:47:09,293 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-11 22:47:09,483 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:47:09,483 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:47:09,484 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:47:09,484 INFO L85 PathProgramCache]: Analyzing trace with hash 1706175702, now seen corresponding path program 10 times [2022-07-11 22:47:09,484 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:47:09,484 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [109986930] [2022-07-11 22:47:09,484 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:47:09,484 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:47:09,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:47:09,562 INFO L134 CoverageAnalysis]: Checked inductivity of 121 backedges. 18 proven. 23 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2022-07-11 22:47:09,562 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:47:09,562 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [109986930] [2022-07-11 22:47:09,562 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [109986930] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:47:09,562 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1404674089] [2022-07-11 22:47:09,563 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-11 22:47:09,563 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:47:09,563 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:47:09,564 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-11 22:47:09,565 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-11 22:47:09,614 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-11 22:47:09,615 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:47:09,615 INFO L263 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-11 22:47:09,616 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:47:09,728 INFO L134 CoverageAnalysis]: Checked inductivity of 121 backedges. 25 proven. 16 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2022-07-11 22:47:09,728 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:47:09,799 INFO L134 CoverageAnalysis]: Checked inductivity of 121 backedges. 25 proven. 16 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2022-07-11 22:47:09,799 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1404674089] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:47:09,799 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:47:09,799 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 20 [2022-07-11 22:47:09,799 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [182438666] [2022-07-11 22:47:09,800 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:47:09,800 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-07-11 22:47:09,800 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:47:09,800 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-07-11 22:47:09,800 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=101, Invalid=279, Unknown=0, NotChecked=0, Total=380 [2022-07-11 22:47:09,801 INFO L87 Difference]: Start difference. First operand 111 states and 121 transitions. Second operand has 20 states, 20 states have (on average 3.15) internal successors, (63), 20 states have internal predecessors, (63), 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-11 22:47:10,092 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:47:10,092 INFO L93 Difference]: Finished difference Result 290 states and 318 transitions. [2022-07-11 22:47:10,093 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-07-11 22:47:10,093 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 3.15) internal successors, (63), 20 states have internal predecessors, (63), 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 77 [2022-07-11 22:47:10,093 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:47:10,093 INFO L225 Difference]: With dead ends: 290 [2022-07-11 22:47:10,094 INFO L226 Difference]: Without dead ends: 137 [2022-07-11 22:47:10,094 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 170 GetRequests, 146 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 155 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=161, Invalid=439, Unknown=0, NotChecked=0, Total=600 [2022-07-11 22:47:10,094 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 213 mSDsluCounter, 29 mSDsCounter, 0 mSdLazyCounter, 401 mSolverCounterSat, 236 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 213 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 637 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 236 IncrementalHoareTripleChecker+Valid, 401 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-11 22:47:10,095 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [213 Valid, 41 Invalid, 637 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [236 Valid, 401 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-11 22:47:10,095 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2022-07-11 22:47:10,103 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 118. [2022-07-11 22:47:10,103 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 117 states have (on average 1.0854700854700854) internal successors, (127), 117 states have internal predecessors, (127), 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-11 22:47:10,104 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 127 transitions. [2022-07-11 22:47:10,104 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 127 transitions. Word has length 77 [2022-07-11 22:47:10,104 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:47:10,104 INFO L495 AbstractCegarLoop]: Abstraction has 118 states and 127 transitions. [2022-07-11 22:47:10,104 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 3.15) internal successors, (63), 20 states have internal predecessors, (63), 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-11 22:47:10,104 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 127 transitions. [2022-07-11 22:47:10,105 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2022-07-11 22:47:10,105 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:47:10,105 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:47:10,121 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-07-11 22:47:10,309 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,SelfDestructingSolverStorable12 [2022-07-11 22:47:10,310 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:47:10,310 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:47:10,310 INFO L85 PathProgramCache]: Analyzing trace with hash 437686490, now seen corresponding path program 11 times [2022-07-11 22:47:10,310 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:47:10,310 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1803852298] [2022-07-11 22:47:10,310 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:47:10,310 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:47:10,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:47:10,390 INFO L134 CoverageAnalysis]: Checked inductivity of 139 backedges. 9 proven. 32 refuted. 0 times theorem prover too weak. 98 trivial. 0 not checked. [2022-07-11 22:47:10,391 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:47:10,391 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1803852298] [2022-07-11 22:47:10,391 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1803852298] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:47:10,391 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [816304033] [2022-07-11 22:47:10,391 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-11 22:47:10,391 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:47:10,391 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:47:10,392 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-11 22:47:10,393 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-11 22:47:10,522 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2022-07-11 22:47:10,522 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:47:10,523 INFO L263 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-11 22:47:10,524 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:47:10,628 INFO L134 CoverageAnalysis]: Checked inductivity of 139 backedges. 16 proven. 25 refuted. 0 times theorem prover too weak. 98 trivial. 0 not checked. [2022-07-11 22:47:10,628 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:47:10,680 INFO L134 CoverageAnalysis]: Checked inductivity of 139 backedges. 16 proven. 25 refuted. 0 times theorem prover too weak. 98 trivial. 0 not checked. [2022-07-11 22:47:10,681 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [816304033] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:47:10,681 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:47:10,681 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 20 [2022-07-11 22:47:10,681 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1430610089] [2022-07-11 22:47:10,681 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:47:10,681 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-07-11 22:47:10,681 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:47:10,682 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-07-11 22:47:10,682 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=101, Invalid=279, Unknown=0, NotChecked=0, Total=380 [2022-07-11 22:47:10,682 INFO L87 Difference]: Start difference. First operand 118 states and 127 transitions. Second operand has 20 states, 20 states have (on average 4.65) internal successors, (93), 20 states have internal predecessors, (93), 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-11 22:47:10,965 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:47:10,965 INFO L93 Difference]: Finished difference Result 130 states and 139 transitions. [2022-07-11 22:47:10,965 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-07-11 22:47:10,966 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 4.65) internal successors, (93), 20 states have internal predecessors, (93), 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 81 [2022-07-11 22:47:10,966 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:47:10,966 INFO L225 Difference]: With dead ends: 130 [2022-07-11 22:47:10,966 INFO L226 Difference]: Without dead ends: 96 [2022-07-11 22:47:10,966 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 189 GetRequests, 159 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 226 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=207, Invalid=663, Unknown=0, NotChecked=0, Total=870 [2022-07-11 22:47:10,967 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 170 mSDsluCounter, 11 mSDsCounter, 0 mSdLazyCounter, 416 mSolverCounterSat, 170 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 170 SdHoareTripleChecker+Valid, 23 SdHoareTripleChecker+Invalid, 586 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 170 IncrementalHoareTripleChecker+Valid, 416 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-11 22:47:10,967 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [170 Valid, 23 Invalid, 586 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [170 Valid, 416 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-11 22:47:10,967 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2022-07-11 22:47:10,974 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 90. [2022-07-11 22:47:10,974 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 89 states have (on average 1.0786516853932584) internal successors, (96), 89 states have internal predecessors, (96), 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-11 22:47:10,974 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 96 transitions. [2022-07-11 22:47:10,974 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 96 transitions. Word has length 81 [2022-07-11 22:47:10,975 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:47:10,975 INFO L495 AbstractCegarLoop]: Abstraction has 90 states and 96 transitions. [2022-07-11 22:47:10,975 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 4.65) internal successors, (93), 20 states have internal predecessors, (93), 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-11 22:47:10,975 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 96 transitions. [2022-07-11 22:47:10,975 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2022-07-11 22:47:10,975 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:47:10,976 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:47:10,995 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-11 22:47:11,183 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,SelfDestructingSolverStorable13 [2022-07-11 22:47:11,184 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:47:11,184 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:47:11,184 INFO L85 PathProgramCache]: Analyzing trace with hash -1296238366, now seen corresponding path program 12 times [2022-07-11 22:47:11,184 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:47:11,184 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1808847785] [2022-07-11 22:47:11,184 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:47:11,184 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:47:11,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:47:16,388 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 2 proven. 173 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-11 22:47:16,388 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:47:16,388 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1808847785] [2022-07-11 22:47:16,388 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1808847785] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:47:16,388 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [61131213] [2022-07-11 22:47:16,388 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-07-11 22:47:16,388 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:47:16,388 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:47:16,389 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-11 22:47:16,390 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-11 22:47:16,458 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 6 check-sat command(s) [2022-07-11 22:47:16,458 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:47:16,460 WARN L261 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 144 conjunts are in the unsatisfiable core [2022-07-11 22:47:16,462 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:47:20,703 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-11 22:47:20,703 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 28 treesize of output 41 [2022-07-11 22:47:20,983 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 3 proven. 171 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-07-11 22:47:20,983 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:47:28,560 INFO L356 Elim1Store]: treesize reduction 387, result has 41.2 percent of original size [2022-07-11 22:47:28,561 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 10 select indices, 10 select index equivalence classes, 0 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 45 case distinctions, treesize of input 88 treesize of output 286 [2022-07-11 22:47:29,182 INFO L356 Elim1Store]: treesize reduction 589, result has 10.5 percent of original size [2022-07-11 22:47:29,183 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 10 select indices, 10 select index equivalence classes, 0 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 45 case distinctions, treesize of input 87 treesize of output 83 [2022-07-11 22:47:29,318 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 0 proven. 159 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-07-11 22:47:29,318 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [61131213] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:47:29,318 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:47:29,319 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [75, 32, 26] total 124 [2022-07-11 22:47:29,320 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [813997161] [2022-07-11 22:47:29,320 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:47:29,320 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 124 states [2022-07-11 22:47:29,320 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:47:29,321 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 124 interpolants. [2022-07-11 22:47:29,321 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=762, Invalid=14490, Unknown=0, NotChecked=0, Total=15252 [2022-07-11 22:47:29,321 INFO L87 Difference]: Start difference. First operand 90 states and 96 transitions. Second operand has 124 states, 124 states have (on average 2.0161290322580645) internal successors, (250), 124 states have internal predecessors, (250), 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-11 22:47:42,230 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:47:42,231 INFO L93 Difference]: Finished difference Result 273 states and 295 transitions. [2022-07-11 22:47:42,231 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 150 states. [2022-07-11 22:47:42,231 INFO L78 Accepts]: Start accepts. Automaton has has 124 states, 124 states have (on average 2.0161290322580645) internal successors, (250), 124 states have internal predecessors, (250), 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 89 [2022-07-11 22:47:42,231 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:47:42,232 INFO L225 Difference]: With dead ends: 273 [2022-07-11 22:47:42,232 INFO L226 Difference]: Without dead ends: 267 [2022-07-11 22:47:42,236 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 355 GetRequests, 101 SyntacticMatches, 35 SemanticMatches, 219 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16979 ImplicationChecksByTransitivity, 25.2s TimeCoverageRelationStatistics Valid=2520, Invalid=46100, Unknown=0, NotChecked=0, Total=48620 [2022-07-11 22:47:42,237 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 34 mSDsluCounter, 190 mSDsCounter, 0 mSdLazyCounter, 2228 mSolverCounterSat, 360 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 201 SdHoareTripleChecker+Invalid, 4373 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 360 IncrementalHoareTripleChecker+Valid, 2228 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 1785 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2022-07-11 22:47:42,238 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 201 Invalid, 4373 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [360 Valid, 2228 Invalid, 0 Unknown, 1785 Unchecked, 1.4s Time] [2022-07-11 22:47:42,238 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 267 states. [2022-07-11 22:47:42,255 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 267 to 157. [2022-07-11 22:47:42,255 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 157 states, 156 states have (on average 1.0897435897435896) internal successors, (170), 156 states have internal predecessors, (170), 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-11 22:47:42,255 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 170 transitions. [2022-07-11 22:47:42,255 INFO L78 Accepts]: Start accepts. Automaton has 157 states and 170 transitions. Word has length 89 [2022-07-11 22:47:42,256 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:47:42,256 INFO L495 AbstractCegarLoop]: Abstraction has 157 states and 170 transitions. [2022-07-11 22:47:42,256 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 124 states, 124 states have (on average 2.0161290322580645) internal successors, (250), 124 states have internal predecessors, (250), 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-11 22:47:42,256 INFO L276 IsEmpty]: Start isEmpty. Operand 157 states and 170 transitions. [2022-07-11 22:47:42,256 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-07-11 22:47:42,256 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:47:42,257 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:47:42,273 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-11 22:47:42,465 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,SelfDestructingSolverStorable14 [2022-07-11 22:47:42,466 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:47:42,466 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:47:42,466 INFO L85 PathProgramCache]: Analyzing trace with hash -91318780, now seen corresponding path program 13 times [2022-07-11 22:47:42,466 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:47:42,466 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [845418300] [2022-07-11 22:47:42,466 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:47:42,466 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:47:42,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:47:42,562 INFO L134 CoverageAnalysis]: Checked inductivity of 186 backedges. 27 proven. 34 refuted. 0 times theorem prover too weak. 125 trivial. 0 not checked. [2022-07-11 22:47:42,562 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:47:42,562 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [845418300] [2022-07-11 22:47:42,562 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [845418300] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:47:42,562 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1833305782] [2022-07-11 22:47:42,562 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-07-11 22:47:42,563 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:47:42,563 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:47:42,564 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-11 22:47:42,565 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-11 22:47:42,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:47:42,627 INFO L263 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-11 22:47:42,628 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:47:42,808 INFO L134 CoverageAnalysis]: Checked inductivity of 186 backedges. 36 proven. 25 refuted. 0 times theorem prover too weak. 125 trivial. 0 not checked. [2022-07-11 22:47:42,809 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:47:42,915 INFO L134 CoverageAnalysis]: Checked inductivity of 186 backedges. 36 proven. 25 refuted. 0 times theorem prover too weak. 125 trivial. 0 not checked. [2022-07-11 22:47:42,915 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1833305782] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:47:42,916 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:47:42,916 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 15] total 23 [2022-07-11 22:47:42,916 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [912278918] [2022-07-11 22:47:42,916 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:47:42,916 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-07-11 22:47:42,916 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:47:42,917 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-07-11 22:47:42,917 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=131, Invalid=375, Unknown=0, NotChecked=0, Total=506 [2022-07-11 22:47:42,917 INFO L87 Difference]: Start difference. First operand 157 states and 170 transitions. Second operand has 23 states, 23 states have (on average 3.0) internal successors, (69), 23 states have internal predecessors, (69), 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-11 22:47:43,299 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:47:43,299 INFO L93 Difference]: Finished difference Result 350 states and 379 transitions. [2022-07-11 22:47:43,299 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-07-11 22:47:43,299 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 3.0) internal successors, (69), 23 states have internal predecessors, (69), 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 91 [2022-07-11 22:47:43,300 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:47:43,300 INFO L225 Difference]: With dead ends: 350 [2022-07-11 22:47:43,300 INFO L226 Difference]: Without dead ends: 170 [2022-07-11 22:47:43,300 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 201 GetRequests, 173 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 211 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=212, Invalid=600, Unknown=0, NotChecked=0, Total=812 [2022-07-11 22:47:43,301 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 220 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 561 mSolverCounterSat, 251 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 220 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 812 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 251 IncrementalHoareTripleChecker+Valid, 561 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-11 22:47:43,301 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [220 Valid, 45 Invalid, 812 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [251 Valid, 561 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-11 22:47:43,301 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 170 states. [2022-07-11 22:47:43,312 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 170 to 150. [2022-07-11 22:47:43,313 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 150 states, 149 states have (on average 1.0738255033557047) internal successors, (160), 149 states have internal predecessors, (160), 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-11 22:47:43,313 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 150 states to 150 states and 160 transitions. [2022-07-11 22:47:43,313 INFO L78 Accepts]: Start accepts. Automaton has 150 states and 160 transitions. Word has length 91 [2022-07-11 22:47:43,313 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:47:43,313 INFO L495 AbstractCegarLoop]: Abstraction has 150 states and 160 transitions. [2022-07-11 22:47:43,313 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 3.0) internal successors, (69), 23 states have internal predecessors, (69), 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-11 22:47:43,314 INFO L276 IsEmpty]: Start isEmpty. Operand 150 states and 160 transitions. [2022-07-11 22:47:43,314 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2022-07-11 22:47:43,314 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:47:43,314 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:47:43,331 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2022-07-11 22:47:43,527 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,SelfDestructingSolverStorable15 [2022-07-11 22:47:43,527 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:47:43,528 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:47:43,528 INFO L85 PathProgramCache]: Analyzing trace with hash 688277478, now seen corresponding path program 14 times [2022-07-11 22:47:43,528 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:47:43,528 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1406021] [2022-07-11 22:47:43,528 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:47:43,528 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:47:43,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:47:43,626 INFO L134 CoverageAnalysis]: Checked inductivity of 197 backedges. 16 proven. 45 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2022-07-11 22:47:43,626 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:47:43,627 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1406021] [2022-07-11 22:47:43,627 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1406021] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:47:43,627 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [633759354] [2022-07-11 22:47:43,627 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-11 22:47:43,627 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:47:43,627 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:47:43,628 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-11 22:47:43,630 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-11 22:47:43,695 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-11 22:47:43,695 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:47:43,697 INFO L263 TraceCheckSpWp]: Trace formula consists of 272 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-11 22:47:43,698 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:47:43,837 INFO L134 CoverageAnalysis]: Checked inductivity of 197 backedges. 25 proven. 36 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2022-07-11 22:47:43,837 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:47:43,889 INFO L134 CoverageAnalysis]: Checked inductivity of 197 backedges. 25 proven. 36 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2022-07-11 22:47:43,889 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [633759354] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:47:43,889 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:47:43,889 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 15] total 23 [2022-07-11 22:47:43,889 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1095646403] [2022-07-11 22:47:43,890 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:47:43,890 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-07-11 22:47:43,890 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:47:43,890 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-07-11 22:47:43,890 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=131, Invalid=375, Unknown=0, NotChecked=0, Total=506 [2022-07-11 22:47:43,890 INFO L87 Difference]: Start difference. First operand 150 states and 160 transitions. Second operand has 23 states, 23 states have (on average 3.0) internal successors, (69), 23 states have internal predecessors, (69), 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-11 22:47:44,252 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:47:44,252 INFO L93 Difference]: Finished difference Result 162 states and 172 transitions. [2022-07-11 22:47:44,252 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2022-07-11 22:47:44,252 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 3.0) internal successors, (69), 23 states have internal predecessors, (69), 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 93 [2022-07-11 22:47:44,252 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:47:44,253 INFO L225 Difference]: With dead ends: 162 [2022-07-11 22:47:44,253 INFO L226 Difference]: Without dead ends: 110 [2022-07-11 22:47:44,253 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 176 SyntacticMatches, 2 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 319 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=275, Invalid=915, Unknown=0, NotChecked=0, Total=1190 [2022-07-11 22:47:44,260 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 206 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 599 mSolverCounterSat, 210 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 206 SdHoareTripleChecker+Valid, 26 SdHoareTripleChecker+Invalid, 809 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 210 IncrementalHoareTripleChecker+Valid, 599 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-11 22:47:44,261 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [206 Valid, 26 Invalid, 809 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [210 Valid, 599 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-11 22:47:44,261 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2022-07-11 22:47:44,276 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 104. [2022-07-11 22:47:44,276 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 103 states have (on average 1.0679611650485437) internal successors, (110), 103 states have internal predecessors, (110), 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-11 22:47:44,276 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 110 transitions. [2022-07-11 22:47:44,277 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 110 transitions. Word has length 93 [2022-07-11 22:47:44,277 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:47:44,277 INFO L495 AbstractCegarLoop]: Abstraction has 104 states and 110 transitions. [2022-07-11 22:47:44,277 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 3.0) internal successors, (69), 23 states have internal predecessors, (69), 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-11 22:47:44,277 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 110 transitions. [2022-07-11 22:47:44,277 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2022-07-11 22:47:44,277 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:47:44,277 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:47:44,293 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-11 22:47:44,481 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:47:44,481 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:47:44,482 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:47:44,482 INFO L85 PathProgramCache]: Analyzing trace with hash -1101361904, now seen corresponding path program 15 times [2022-07-11 22:47:44,482 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:47:44,482 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1959983646] [2022-07-11 22:47:44,482 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:47:44,482 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:47:44,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:47:51,635 INFO L134 CoverageAnalysis]: Checked inductivity of 252 backedges. 2 proven. 250 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-11 22:47:51,636 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:47:51,636 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1959983646] [2022-07-11 22:47:51,636 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1959983646] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:47:51,636 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [859903673] [2022-07-11 22:47:51,636 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-11 22:47:51,636 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:47:51,636 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:47:51,637 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-11 22:47:51,638 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-11 22:47:51,732 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2022-07-11 22:47:51,733 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:47:51,736 WARN L261 TraceCheckSpWp]: Trace formula consists of 297 conjuncts, 172 conjunts are in the unsatisfiable core [2022-07-11 22:47:51,739 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:47:51,830 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 15 treesize of output 11 [2022-07-11 22:47:57,834 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:47:57,837 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:47:57,841 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:47:57,841 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:47:57,842 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:47:57,843 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:47:57,844 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:47:57,845 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:47:57,845 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:47:57,885 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-11 22:47:57,885 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 7 select indices, 7 select index equivalence classes, 9 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 64 treesize of output 169 [2022-07-11 22:47:58,395 INFO L134 CoverageAnalysis]: Checked inductivity of 252 backedges. 7 proven. 236 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-07-11 22:47:58,396 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:48:11,777 INFO L134 CoverageAnalysis]: Checked inductivity of 252 backedges. 0 proven. 227 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2022-07-11 22:48:11,777 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [859903673] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:48:11,777 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:48:11,777 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [88, 35, 29] total 143 [2022-07-11 22:48:11,778 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1484437848] [2022-07-11 22:48:11,778 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:48:11,778 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 143 states [2022-07-11 22:48:11,778 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:48:11,778 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 143 interpolants. [2022-07-11 22:48:11,779 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1002, Invalid=19304, Unknown=0, NotChecked=0, Total=20306 [2022-07-11 22:48:11,780 INFO L87 Difference]: Start difference. First operand 104 states and 110 transitions. Second operand has 143 states, 143 states have (on average 2.0) internal successors, (286), 143 states have internal predecessors, (286), 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-11 22:48:32,759 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:48:32,759 INFO L93 Difference]: Finished difference Result 198 states and 211 transitions. [2022-07-11 22:48:32,760 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 121 states. [2022-07-11 22:48:32,760 INFO L78 Accepts]: Start accepts. Automaton has has 143 states, 143 states have (on average 2.0) internal successors, (286), 143 states have internal predecessors, (286), 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 103 [2022-07-11 22:48:32,760 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:48:32,761 INFO L225 Difference]: With dead ends: 198 [2022-07-11 22:48:32,761 INFO L226 Difference]: Without dead ends: 194 [2022-07-11 22:48:32,763 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 404 GetRequests, 121 SyntacticMatches, 41 SemanticMatches, 242 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 18125 ImplicationChecksByTransitivity, 42.1s TimeCoverageRelationStatistics Valid=3128, Invalid=56164, Unknown=0, NotChecked=0, Total=59292 [2022-07-11 22:48:32,763 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 56 mSDsluCounter, 205 mSDsCounter, 0 mSdLazyCounter, 2656 mSolverCounterSat, 339 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 216 SdHoareTripleChecker+Invalid, 4553 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 339 IncrementalHoareTripleChecker+Valid, 2656 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 1558 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2022-07-11 22:48:32,764 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 216 Invalid, 4553 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [339 Valid, 2656 Invalid, 0 Unknown, 1558 Unchecked, 1.6s Time] [2022-07-11 22:48:32,764 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 194 states. [2022-07-11 22:48:32,781 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 194 to 151. [2022-07-11 22:48:32,781 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 151 states, 150 states have (on average 1.0733333333333333) internal successors, (161), 150 states have internal predecessors, (161), 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-11 22:48:32,782 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 151 states to 151 states and 161 transitions. [2022-07-11 22:48:32,782 INFO L78 Accepts]: Start accepts. Automaton has 151 states and 161 transitions. Word has length 103 [2022-07-11 22:48:32,782 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:48:32,782 INFO L495 AbstractCegarLoop]: Abstraction has 151 states and 161 transitions. [2022-07-11 22:48:32,782 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 143 states, 143 states have (on average 2.0) internal successors, (286), 143 states have internal predecessors, (286), 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-11 22:48:32,782 INFO L276 IsEmpty]: Start isEmpty. Operand 151 states and 161 transitions. [2022-07-11 22:48:32,783 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2022-07-11 22:48:32,783 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:48:32,783 INFO L195 NwaCegarLoop]: trace histogram [7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:48:32,799 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-11 22:48:32,983 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,SelfDestructingSolverStorable17 [2022-07-11 22:48:32,984 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:48:32,984 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:48:32,984 INFO L85 PathProgramCache]: Analyzing trace with hash -1793599822, now seen corresponding path program 16 times [2022-07-11 22:48:32,984 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:48:32,984 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [647868103] [2022-07-11 22:48:32,984 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:48:32,984 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:48:32,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:48:33,112 INFO L134 CoverageAnalysis]: Checked inductivity of 265 backedges. 38 proven. 47 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-07-11 22:48:33,112 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:48:33,112 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [647868103] [2022-07-11 22:48:33,112 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [647868103] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:48:33,112 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [211713422] [2022-07-11 22:48:33,112 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-11 22:48:33,112 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:48:33,113 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:48:33,114 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-11 22:48:33,115 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-11 22:48:33,180 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-11 22:48:33,181 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:48:33,182 INFO L263 TraceCheckSpWp]: Trace formula consists of 273 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-11 22:48:33,183 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:48:33,367 INFO L134 CoverageAnalysis]: Checked inductivity of 265 backedges. 49 proven. 36 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-07-11 22:48:33,367 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:48:33,459 INFO L134 CoverageAnalysis]: Checked inductivity of 265 backedges. 49 proven. 36 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-07-11 22:48:33,459 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [211713422] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:48:33,459 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:48:33,459 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 17] total 26 [2022-07-11 22:48:33,459 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1047615977] [2022-07-11 22:48:33,459 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:48:33,460 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-07-11 22:48:33,460 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:48:33,460 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-07-11 22:48:33,460 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=165, Invalid=485, Unknown=0, NotChecked=0, Total=650 [2022-07-11 22:48:33,460 INFO L87 Difference]: Start difference. First operand 151 states and 161 transitions. Second operand has 26 states, 26 states have (on average 2.8846153846153846) internal successors, (75), 26 states have internal predecessors, (75), 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-11 22:48:33,901 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:48:33,902 INFO L93 Difference]: Finished difference Result 386 states and 414 transitions. [2022-07-11 22:48:33,902 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2022-07-11 22:48:33,902 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 2.8846153846153846) internal successors, (75), 26 states have internal predecessors, (75), 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 105 [2022-07-11 22:48:33,902 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:48:33,903 INFO L225 Difference]: With dead ends: 386 [2022-07-11 22:48:33,903 INFO L226 Difference]: Without dead ends: 177 [2022-07-11 22:48:33,903 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 232 GetRequests, 200 SyntacticMatches, 1 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 275 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=270, Invalid=786, Unknown=0, NotChecked=0, Total=1056 [2022-07-11 22:48:33,904 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 411 mSDsluCounter, 25 mSDsCounter, 0 mSdLazyCounter, 680 mSolverCounterSat, 411 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 411 SdHoareTripleChecker+Valid, 37 SdHoareTripleChecker+Invalid, 1091 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 411 IncrementalHoareTripleChecker+Valid, 680 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-07-11 22:48:33,904 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [411 Valid, 37 Invalid, 1091 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [411 Valid, 680 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-07-11 22:48:33,904 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2022-07-11 22:48:33,921 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 158. [2022-07-11 22:48:33,921 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 158 states, 157 states have (on average 1.0636942675159236) internal successors, (167), 157 states have internal predecessors, (167), 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-11 22:48:33,922 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 167 transitions. [2022-07-11 22:48:33,922 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 167 transitions. Word has length 105 [2022-07-11 22:48:33,922 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:48:33,922 INFO L495 AbstractCegarLoop]: Abstraction has 158 states and 167 transitions. [2022-07-11 22:48:33,922 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 2.8846153846153846) internal successors, (75), 26 states have internal predecessors, (75), 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-11 22:48:33,922 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 167 transitions. [2022-07-11 22:48:33,923 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2022-07-11 22:48:33,923 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:48:33,923 INFO L195 NwaCegarLoop]: trace histogram [7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:48:33,939 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-07-11 22:48:34,129 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:48:34,129 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:48:34,130 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:48:34,130 INFO L85 PathProgramCache]: Analyzing trace with hash -1629639498, now seen corresponding path program 17 times [2022-07-11 22:48:34,130 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:48:34,130 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [528537818] [2022-07-11 22:48:34,130 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:48:34,130 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:48:34,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:48:34,242 INFO L134 CoverageAnalysis]: Checked inductivity of 291 backedges. 25 proven. 60 refuted. 0 times theorem prover too weak. 206 trivial. 0 not checked. [2022-07-11 22:48:34,242 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:48:34,242 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [528537818] [2022-07-11 22:48:34,242 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [528537818] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:48:34,242 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1142848274] [2022-07-11 22:48:34,242 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-11 22:48:34,242 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:48:34,243 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:48:34,244 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-11 22:48:34,245 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-07-11 22:48:34,691 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2022-07-11 22:48:34,691 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:48:34,693 INFO L263 TraceCheckSpWp]: Trace formula consists of 314 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-11 22:48:34,694 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:48:34,883 INFO L134 CoverageAnalysis]: Checked inductivity of 291 backedges. 36 proven. 49 refuted. 0 times theorem prover too weak. 206 trivial. 0 not checked. [2022-07-11 22:48:34,884 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:48:34,981 INFO L134 CoverageAnalysis]: Checked inductivity of 291 backedges. 36 proven. 49 refuted. 0 times theorem prover too weak. 206 trivial. 0 not checked. [2022-07-11 22:48:34,981 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1142848274] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:48:34,981 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:48:34,981 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 17] total 26 [2022-07-11 22:48:34,981 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [211448731] [2022-07-11 22:48:34,981 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:48:34,981 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-07-11 22:48:34,981 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:48:34,982 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-07-11 22:48:34,982 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=165, Invalid=485, Unknown=0, NotChecked=0, Total=650 [2022-07-11 22:48:34,982 INFO L87 Difference]: Start difference. First operand 158 states and 167 transitions. Second operand has 26 states, 26 states have (on average 3.769230769230769) internal successors, (98), 26 states have internal predecessors, (98), 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-11 22:48:35,378 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-11 22:48:35,378 INFO L93 Difference]: Finished difference Result 170 states and 179 transitions. [2022-07-11 22:48:35,378 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-07-11 22:48:35,379 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 3.769230769230769) internal successors, (98), 26 states have internal predecessors, (98), 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 109 [2022-07-11 22:48:35,379 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-11 22:48:35,379 INFO L225 Difference]: With dead ends: 170 [2022-07-11 22:48:35,379 INFO L226 Difference]: Without dead ends: 124 [2022-07-11 22:48:35,379 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 247 GetRequests, 207 SyntacticMatches, 2 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 427 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=353, Invalid=1207, Unknown=0, NotChecked=0, Total=1560 [2022-07-11 22:48:35,380 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 238 mSDsluCounter, 21 mSDsCounter, 0 mSdLazyCounter, 682 mSolverCounterSat, 222 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 238 SdHoareTripleChecker+Valid, 33 SdHoareTripleChecker+Invalid, 904 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 222 IncrementalHoareTripleChecker+Valid, 682 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-11 22:48:35,381 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [238 Valid, 33 Invalid, 904 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [222 Valid, 682 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-11 22:48:35,381 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2022-07-11 22:48:35,394 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 118. [2022-07-11 22:48:35,394 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 117 states have (on average 1.0598290598290598) internal successors, (124), 117 states have internal predecessors, (124), 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-11 22:48:35,395 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 124 transitions. [2022-07-11 22:48:35,395 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 124 transitions. Word has length 109 [2022-07-11 22:48:35,395 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-11 22:48:35,395 INFO L495 AbstractCegarLoop]: Abstraction has 118 states and 124 transitions. [2022-07-11 22:48:35,395 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 3.769230769230769) internal successors, (98), 26 states have internal predecessors, (98), 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-11 22:48:35,395 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 124 transitions. [2022-07-11 22:48:35,396 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2022-07-11 22:48:35,396 INFO L187 NwaCegarLoop]: Found error trace [2022-07-11 22:48:35,396 INFO L195 NwaCegarLoop]: trace histogram [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-11 22:48:35,412 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-07-11 22:48:35,598 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:48:35,598 INFO L420 AbstractCegarLoop]: === Iteration 21 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-11 22:48:35,599 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-11 22:48:35,599 INFO L85 PathProgramCache]: Analyzing trace with hash 680376510, now seen corresponding path program 18 times [2022-07-11 22:48:35,599 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-11 22:48:35,599 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1194426233] [2022-07-11 22:48:35,599 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-11 22:48:35,599 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-11 22:48:35,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-11 22:48:45,614 INFO L134 CoverageAnalysis]: Checked inductivity of 343 backedges. 20 proven. 323 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-11 22:48:45,614 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-11 22:48:45,615 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1194426233] [2022-07-11 22:48:45,615 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1194426233] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-11 22:48:45,615 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [518155179] [2022-07-11 22:48:45,615 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-07-11 22:48:45,615 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-11 22:48:45,615 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-11 22:48:45,616 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-11 22:48:45,617 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-07-11 22:48:45,738 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2022-07-11 22:48:45,739 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-11 22:48:45,742 WARN L261 TraceCheckSpWp]: Trace formula consists of 334 conjuncts, 196 conjunts are in the unsatisfiable core [2022-07-11 22:48:45,744 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-11 22:48:59,900 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,903 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,904 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,904 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,905 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,906 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,907 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,907 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,911 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,911 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,912 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,913 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,914 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,915 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,916 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,916 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,918 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,918 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,919 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,920 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,921 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,922 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,923 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,924 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,925 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,925 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,927 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,927 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,928 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,929 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-11 22:48:59,986 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-11 22:48:59,986 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 10 select indices, 10 select index equivalence classes, 30 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 45 case distinctions, treesize of input 98 treesize of output 251 [2022-07-11 22:49:00,488 INFO L134 CoverageAnalysis]: Checked inductivity of 343 backedges. 11 proven. 307 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2022-07-11 22:49:00,488 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-11 22:49:17,349 INFO L356 Elim1Store]: treesize reduction 1183, result has 20.9 percent of original size [2022-07-11 22:49:17,349 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 14 select indices, 14 select index equivalence classes, 0 disjoint index pairs (out of 91 index pairs), introduced 14 new quantified variables, introduced 91 case distinctions, treesize of input 133 treesize of output 331 [2022-07-11 22:49:17,903 INFO L356 Elim1Store]: treesize reduction 1341, result has 10.4 percent of original size [2022-07-11 22:49:17,904 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 14 select indices, 14 select index equivalence classes, 0 disjoint index pairs (out of 91 index pairs), introduced 14 new quantified variables, introduced 91 case distinctions, treesize of input 134 treesize of output 174 [2022-07-11 22:49:18,115 INFO L134 CoverageAnalysis]: Checked inductivity of 343 backedges. 0 proven. 307 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2022-07-11 22:49:18,115 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [518155179] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-11 22:49:18,115 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-11 22:49:18,115 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [103, 38, 34] total 167 [2022-07-11 22:49:18,115 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [979251102] [2022-07-11 22:49:18,115 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-11 22:49:18,116 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 167 states [2022-07-11 22:49:18,116 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-11 22:49:18,116 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 167 interpolants. [2022-07-11 22:49:18,117 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1285, Invalid=26436, Unknown=1, NotChecked=0, Total=27722 [2022-07-11 22:49:18,118 INFO L87 Difference]: Start difference. First operand 118 states and 124 transitions. Second operand has 167 states, 167 states have (on average 1.9341317365269461) internal successors, (323), 167 states have internal predecessors, (323), 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)