./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/loops/eureka_01-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 9a8b2e8d 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.3.100.v20150511-1540.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/loops/eureka_01-1.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 a0175e46c372a5de5baa3319396a86b21fa2d79f ..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE --- Real Ultimate output --- This is Ultimate 0.1.25-9a8b2e8 [2020-10-20 00:53:35,156 INFO L177 SettingsManager]: Resetting all preferences to default values... [2020-10-20 00:53:35,159 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2020-10-20 00:53:35,199 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2020-10-20 00:53:35,199 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2020-10-20 00:53:35,209 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2020-10-20 00:53:35,212 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2020-10-20 00:53:35,215 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2020-10-20 00:53:35,218 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2020-10-20 00:53:35,221 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2020-10-20 00:53:35,222 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2020-10-20 00:53:35,224 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2020-10-20 00:53:35,224 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2020-10-20 00:53:35,228 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2020-10-20 00:53:35,229 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2020-10-20 00:53:35,239 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2020-10-20 00:53:35,241 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2020-10-20 00:53:35,242 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2020-10-20 00:53:35,244 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2020-10-20 00:53:35,251 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2020-10-20 00:53:35,254 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2020-10-20 00:53:35,255 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2020-10-20 00:53:35,257 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2020-10-20 00:53:35,258 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2020-10-20 00:53:35,269 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2020-10-20 00:53:35,276 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2020-10-20 00:53:35,276 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2020-10-20 00:53:35,279 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2020-10-20 00:53:35,279 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2020-10-20 00:53:35,280 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2020-10-20 00:53:35,281 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2020-10-20 00:53:35,281 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2020-10-20 00:53:35,284 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2020-10-20 00:53:35,285 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2020-10-20 00:53:35,286 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2020-10-20 00:53:35,287 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2020-10-20 00:53:35,288 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2020-10-20 00:53:35,289 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2020-10-20 00:53:35,290 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2020-10-20 00:53:35,291 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2020-10-20 00:53:35,291 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2020-10-20 00:53:35,293 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2020-10-20 00:53:35,329 INFO L113 SettingsManager]: Loading preferences was successful [2020-10-20 00:53:35,329 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2020-10-20 00:53:35,331 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2020-10-20 00:53:35,332 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2020-10-20 00:53:35,332 INFO L138 SettingsManager]: * Use SBE=true [2020-10-20 00:53:35,332 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2020-10-20 00:53:35,332 INFO L138 SettingsManager]: * sizeof long=4 [2020-10-20 00:53:35,333 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2020-10-20 00:53:35,333 INFO L138 SettingsManager]: * sizeof POINTER=4 [2020-10-20 00:53:35,333 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2020-10-20 00:53:35,334 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2020-10-20 00:53:35,334 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2020-10-20 00:53:35,335 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2020-10-20 00:53:35,335 INFO L138 SettingsManager]: * sizeof long double=12 [2020-10-20 00:53:35,335 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2020-10-20 00:53:35,336 INFO L138 SettingsManager]: * Use constant arrays=true [2020-10-20 00:53:35,336 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2020-10-20 00:53:35,336 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2020-10-20 00:53:35,336 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2020-10-20 00:53:35,337 INFO L138 SettingsManager]: * To the following directory=./dump/ [2020-10-20 00:53:35,337 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2020-10-20 00:53:35,337 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2020-10-20 00:53:35,337 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2020-10-20 00:53:35,338 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2020-10-20 00:53:35,338 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2020-10-20 00:53:35,338 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2020-10-20 00:53:35,338 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2020-10-20 00:53:35,339 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2020-10-20 00:53:35,339 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2020-10-20 00:53:35,339 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode 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 -> a0175e46c372a5de5baa3319396a86b21fa2d79f [2020-10-20 00:53:35,554 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2020-10-20 00:53:35,568 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2020-10-20 00:53:35,571 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2020-10-20 00:53:35,573 INFO L271 PluginConnector]: Initializing CDTParser... [2020-10-20 00:53:35,580 INFO L275 PluginConnector]: CDTParser initialized [2020-10-20 00:53:35,581 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/loops/eureka_01-1.c [2020-10-20 00:53:35,642 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/849659096/181b176e536245f18c74d31f456b341d/FLAG1a6101a3e [2020-10-20 00:53:36,191 INFO L306 CDTParser]: Found 1 translation units. [2020-10-20 00:53:36,192 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/loops/eureka_01-1.c [2020-10-20 00:53:36,199 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/849659096/181b176e536245f18c74d31f456b341d/FLAG1a6101a3e [2020-10-20 00:53:36,604 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/849659096/181b176e536245f18c74d31f456b341d [2020-10-20 00:53:36,608 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2020-10-20 00:53:36,615 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2020-10-20 00:53:36,618 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2020-10-20 00:53:36,619 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2020-10-20 00:53:36,622 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2020-10-20 00:53:36,623 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.10 12:53:36" (1/1) ... [2020-10-20 00:53:36,627 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@427877d7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.10 12:53:36, skipping insertion in model container [2020-10-20 00:53:36,628 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.10 12:53:36" (1/1) ... [2020-10-20 00:53:36,636 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2020-10-20 00:53:36,657 INFO L178 MainTranslator]: Built tables and reachable declarations [2020-10-20 00:53:36,892 INFO L206 PostProcessor]: Analyzing one entry point: main [2020-10-20 00:53:36,901 INFO L203 MainTranslator]: Completed pre-run [2020-10-20 00:53:36,943 INFO L206 PostProcessor]: Analyzing one entry point: main [2020-10-20 00:53:36,960 INFO L208 MainTranslator]: Completed translation [2020-10-20 00:53:36,961 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.10 12:53:36 WrapperNode [2020-10-20 00:53:36,961 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2020-10-20 00:53:36,962 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2020-10-20 00:53:36,962 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2020-10-20 00:53:36,962 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2020-10-20 00:53:36,970 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.10 12:53:36" (1/1) ... [2020-10-20 00:53:36,981 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.10 12:53:36" (1/1) ... [2020-10-20 00:53:37,010 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2020-10-20 00:53:37,011 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2020-10-20 00:53:37,011 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2020-10-20 00:53:37,011 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2020-10-20 00:53:37,021 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.10 12:53:36" (1/1) ... [2020-10-20 00:53:37,021 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.10 12:53:36" (1/1) ... [2020-10-20 00:53:37,025 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.10 12:53:36" (1/1) ... [2020-10-20 00:53:37,025 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.10 12:53:36" (1/1) ... [2020-10-20 00:53:37,035 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.10 12:53:36" (1/1) ... [2020-10-20 00:53:37,049 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.10 12:53:36" (1/1) ... [2020-10-20 00:53:37,051 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.10 12:53:36" (1/1) ... [2020-10-20 00:53:37,054 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2020-10-20 00:53:37,055 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2020-10-20 00:53:37,055 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2020-10-20 00:53:37,055 INFO L275 PluginConnector]: RCFGBuilder initialized [2020-10-20 00:53:37,056 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.10 12:53:36" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2020-10-20 00:53:37,134 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2020-10-20 00:53:37,134 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2020-10-20 00:53:37,134 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2020-10-20 00:53:37,135 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2020-10-20 00:53:37,136 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2020-10-20 00:53:37,136 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2020-10-20 00:53:37,136 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2020-10-20 00:53:37,609 INFO L293 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2020-10-20 00:53:37,609 INFO L298 CfgBuilder]: Removed 13 assume(true) statements. [2020-10-20 00:53:37,611 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.10 12:53:37 BoogieIcfgContainer [2020-10-20 00:53:37,611 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2020-10-20 00:53:37,613 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2020-10-20 00:53:37,613 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2020-10-20 00:53:37,616 INFO L275 PluginConnector]: TraceAbstraction initialized [2020-10-20 00:53:37,619 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.10 12:53:36" (1/3) ... [2020-10-20 00:53:37,620 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@63603406 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.10 12:53:37, skipping insertion in model container [2020-10-20 00:53:37,620 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.10 12:53:36" (2/3) ... [2020-10-20 00:53:37,620 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@63603406 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.10 12:53:37, skipping insertion in model container [2020-10-20 00:53:37,622 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.10 12:53:37" (3/3) ... [2020-10-20 00:53:37,624 INFO L111 eAbstractionObserver]: Analyzing ICFG eureka_01-1.c [2020-10-20 00:53:37,636 INFO L164 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2020-10-20 00:53:37,643 INFO L176 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2020-10-20 00:53:37,653 INFO L253 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2020-10-20 00:53:37,674 INFO L377 AbstractCegarLoop]: Interprodecural is true [2020-10-20 00:53:37,675 INFO L378 AbstractCegarLoop]: Hoare is true [2020-10-20 00:53:37,675 INFO L379 AbstractCegarLoop]: Compute interpolants for FPandBP [2020-10-20 00:53:37,675 INFO L380 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2020-10-20 00:53:37,675 INFO L381 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2020-10-20 00:53:37,676 INFO L382 AbstractCegarLoop]: Difference is false [2020-10-20 00:53:37,676 INFO L383 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2020-10-20 00:53:37,676 INFO L387 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2020-10-20 00:53:37,688 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states. [2020-10-20 00:53:37,693 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2020-10-20 00:53:37,693 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:53:37,694 INFO L422 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:53:37,695 INFO L429 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:53:37,699 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:53:37,699 INFO L82 PathProgramCache]: Analyzing trace with hash -1963003136, now seen corresponding path program 1 times [2020-10-20 00:53:37,707 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:53:37,714 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [891320567] [2020-10-20 00:53:37,715 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:53:37,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:38,010 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-10-20 00:53:38,011 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [891320567] [2020-10-20 00:53:38,012 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2020-10-20 00:53:38,013 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2020-10-20 00:53:38,014 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1434143940] [2020-10-20 00:53:38,023 INFO L461 AbstractCegarLoop]: Interpolant automaton has 5 states [2020-10-20 00:53:38,023 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:53:38,035 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2020-10-20 00:53:38,036 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2020-10-20 00:53:38,038 INFO L87 Difference]: Start difference. First operand 29 states. Second operand 5 states. [2020-10-20 00:53:38,185 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:53:38,186 INFO L93 Difference]: Finished difference Result 90 states and 136 transitions. [2020-10-20 00:53:38,187 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2020-10-20 00:53:38,188 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 13 [2020-10-20 00:53:38,188 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:53:38,199 INFO L225 Difference]: With dead ends: 90 [2020-10-20 00:53:38,199 INFO L226 Difference]: Without dead ends: 42 [2020-10-20 00:53:38,203 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2020-10-20 00:53:38,217 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2020-10-20 00:53:38,232 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 26. [2020-10-20 00:53:38,234 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2020-10-20 00:53:38,234 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 32 transitions. [2020-10-20 00:53:38,236 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 32 transitions. Word has length 13 [2020-10-20 00:53:38,236 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:53:38,236 INFO L481 AbstractCegarLoop]: Abstraction has 26 states and 32 transitions. [2020-10-20 00:53:38,237 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2020-10-20 00:53:38,237 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 32 transitions. [2020-10-20 00:53:38,237 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2020-10-20 00:53:38,238 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:53:38,238 INFO L422 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:53:38,238 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2020-10-20 00:53:38,238 INFO L429 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:53:38,239 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:53:38,239 INFO L82 PathProgramCache]: Analyzing trace with hash 629591390, now seen corresponding path program 1 times [2020-10-20 00:53:38,239 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:53:38,239 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [463925370] [2020-10-20 00:53:38,240 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:53:38,309 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:38,514 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:53:38,514 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [463925370] [2020-10-20 00:53:38,515 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [988394876] [2020-10-20 00:53:38,515 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:38,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:38,637 INFO L263 TraceCheckSpWp]: Trace formula consists of 226 conjuncts, 9 conjunts are in the unsatisfiable core [2020-10-20 00:53:38,645 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:53:38,732 INFO L384 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 11 treesize of output 7 [2020-10-20 00:53:38,736 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:53:38,740 INFO L625 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:53:38,741 INFO L545 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:53:38,741 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:11, output treesize:7 [2020-10-20 00:53:38,817 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:38,824 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:38,847 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:53:38,847 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:53:38,848 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2020-10-20 00:53:38,849 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [735175620] [2020-10-20 00:53:38,850 INFO L461 AbstractCegarLoop]: Interpolant automaton has 10 states [2020-10-20 00:53:38,850 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:53:38,850 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2020-10-20 00:53:38,851 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=63, Unknown=0, NotChecked=0, Total=90 [2020-10-20 00:53:38,851 INFO L87 Difference]: Start difference. First operand 26 states and 32 transitions. Second operand 10 states. [2020-10-20 00:53:39,109 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:53:39,110 INFO L93 Difference]: Finished difference Result 83 states and 104 transitions. [2020-10-20 00:53:39,110 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2020-10-20 00:53:39,110 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 19 [2020-10-20 00:53:39,111 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:53:39,112 INFO L225 Difference]: With dead ends: 83 [2020-10-20 00:53:39,113 INFO L226 Difference]: Without dead ends: 81 [2020-10-20 00:53:39,114 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=56, Invalid=126, Unknown=0, NotChecked=0, Total=182 [2020-10-20 00:53:39,115 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2020-10-20 00:53:39,123 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 43. [2020-10-20 00:53:39,123 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 43 states. [2020-10-20 00:53:39,124 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 55 transitions. [2020-10-20 00:53:39,125 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 55 transitions. Word has length 19 [2020-10-20 00:53:39,125 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:53:39,125 INFO L481 AbstractCegarLoop]: Abstraction has 43 states and 55 transitions. [2020-10-20 00:53:39,125 INFO L482 AbstractCegarLoop]: Interpolant automaton has 10 states. [2020-10-20 00:53:39,125 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 55 transitions. [2020-10-20 00:53:39,126 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2020-10-20 00:53:39,126 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:53:39,127 INFO L422 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:53:39,339 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2020-10-20 00:53:39,340 INFO L429 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:53:39,341 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:53:39,341 INFO L82 PathProgramCache]: Analyzing trace with hash -381525860, now seen corresponding path program 1 times [2020-10-20 00:53:39,342 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:53:39,342 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [752024269] [2020-10-20 00:53:39,343 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:53:39,375 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:39,430 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:53:39,432 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [752024269] [2020-10-20 00:53:39,432 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2020-10-20 00:53:39,432 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2020-10-20 00:53:39,433 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [187680011] [2020-10-20 00:53:39,433 INFO L461 AbstractCegarLoop]: Interpolant automaton has 3 states [2020-10-20 00:53:39,433 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:53:39,433 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2020-10-20 00:53:39,434 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2020-10-20 00:53:39,434 INFO L87 Difference]: Start difference. First operand 43 states and 55 transitions. Second operand 3 states. [2020-10-20 00:53:39,482 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:53:39,482 INFO L93 Difference]: Finished difference Result 66 states and 85 transitions. [2020-10-20 00:53:39,483 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2020-10-20 00:53:39,483 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 19 [2020-10-20 00:53:39,484 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:53:39,485 INFO L225 Difference]: With dead ends: 66 [2020-10-20 00:53:39,485 INFO L226 Difference]: Without dead ends: 45 [2020-10-20 00:53:39,485 INFO L677 BasicCegarLoop]: 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 [2020-10-20 00:53:39,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2020-10-20 00:53:39,500 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 44. [2020-10-20 00:53:39,500 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 44 states. [2020-10-20 00:53:39,501 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 56 transitions. [2020-10-20 00:53:39,503 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 56 transitions. Word has length 19 [2020-10-20 00:53:39,503 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:53:39,503 INFO L481 AbstractCegarLoop]: Abstraction has 44 states and 56 transitions. [2020-10-20 00:53:39,504 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2020-10-20 00:53:39,504 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 56 transitions. [2020-10-20 00:53:39,505 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2020-10-20 00:53:39,505 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:53:39,506 INFO L422 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:53:39,506 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2020-10-20 00:53:39,506 INFO L429 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:53:39,507 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:53:39,507 INFO L82 PathProgramCache]: Analyzing trace with hash 1960843935, now seen corresponding path program 1 times [2020-10-20 00:53:39,507 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:53:39,508 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [897638474] [2020-10-20 00:53:39,508 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:53:39,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:39,628 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:53:39,630 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [897638474] [2020-10-20 00:53:39,630 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2039929506] [2020-10-20 00:53:39,630 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:39,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:39,724 INFO L263 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 4 conjunts are in the unsatisfiable core [2020-10-20 00:53:39,728 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:53:39,769 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:53:39,769 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:53:39,770 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 7 [2020-10-20 00:53:39,770 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1071999280] [2020-10-20 00:53:39,771 INFO L461 AbstractCegarLoop]: Interpolant automaton has 7 states [2020-10-20 00:53:39,771 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:53:39,771 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2020-10-20 00:53:39,772 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2020-10-20 00:53:39,772 INFO L87 Difference]: Start difference. First operand 44 states and 56 transitions. Second operand 7 states. [2020-10-20 00:53:39,930 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:53:39,930 INFO L93 Difference]: Finished difference Result 114 states and 146 transitions. [2020-10-20 00:53:39,931 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2020-10-20 00:53:39,931 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 22 [2020-10-20 00:53:39,932 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:53:39,933 INFO L225 Difference]: With dead ends: 114 [2020-10-20 00:53:39,933 INFO L226 Difference]: Without dead ends: 86 [2020-10-20 00:53:39,934 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=32, Invalid=58, Unknown=0, NotChecked=0, Total=90 [2020-10-20 00:53:39,935 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2020-10-20 00:53:39,943 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 56. [2020-10-20 00:53:39,943 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2020-10-20 00:53:39,944 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 72 transitions. [2020-10-20 00:53:39,944 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 72 transitions. Word has length 22 [2020-10-20 00:53:39,945 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:53:39,945 INFO L481 AbstractCegarLoop]: Abstraction has 56 states and 72 transitions. [2020-10-20 00:53:39,945 INFO L482 AbstractCegarLoop]: Interpolant automaton has 7 states. [2020-10-20 00:53:39,945 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 72 transitions. [2020-10-20 00:53:39,946 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2020-10-20 00:53:39,947 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:53:39,947 INFO L422 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:53:40,160 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:40,161 INFO L429 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:53:40,162 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:53:40,162 INFO L82 PathProgramCache]: Analyzing trace with hash 1926841972, now seen corresponding path program 1 times [2020-10-20 00:53:40,162 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:53:40,163 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [155312245] [2020-10-20 00:53:40,164 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:53:40,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:40,226 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-10-20 00:53:40,227 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [155312245] [2020-10-20 00:53:40,227 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1494425917] [2020-10-20 00:53:40,227 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:40,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:40,306 INFO L263 TraceCheckSpWp]: Trace formula consists of 231 conjuncts, 6 conjunts are in the unsatisfiable core [2020-10-20 00:53:40,308 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:53:40,355 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-10-20 00:53:40,355 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:53:40,355 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2020-10-20 00:53:40,356 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1657602746] [2020-10-20 00:53:40,356 INFO L461 AbstractCegarLoop]: Interpolant automaton has 10 states [2020-10-20 00:53:40,356 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:53:40,357 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2020-10-20 00:53:40,357 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2020-10-20 00:53:40,357 INFO L87 Difference]: Start difference. First operand 56 states and 72 transitions. Second operand 10 states. [2020-10-20 00:53:40,590 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:53:40,590 INFO L93 Difference]: Finished difference Result 181 states and 231 transitions. [2020-10-20 00:53:40,591 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2020-10-20 00:53:40,591 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 22 [2020-10-20 00:53:40,591 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:53:40,592 INFO L225 Difference]: With dead ends: 181 [2020-10-20 00:53:40,593 INFO L226 Difference]: Without dead ends: 159 [2020-10-20 00:53:40,593 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=57, Invalid=125, Unknown=0, NotChecked=0, Total=182 [2020-10-20 00:53:40,594 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 159 states. [2020-10-20 00:53:40,607 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 159 to 75. [2020-10-20 00:53:40,611 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2020-10-20 00:53:40,612 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 98 transitions. [2020-10-20 00:53:40,614 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 98 transitions. Word has length 22 [2020-10-20 00:53:40,614 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:53:40,615 INFO L481 AbstractCegarLoop]: Abstraction has 75 states and 98 transitions. [2020-10-20 00:53:40,617 INFO L482 AbstractCegarLoop]: Interpolant automaton has 10 states. [2020-10-20 00:53:40,617 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 98 transitions. [2020-10-20 00:53:40,619 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2020-10-20 00:53:40,620 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:53:40,620 INFO L422 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:53:40,835 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:40,836 INFO L429 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:53:40,836 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:53:40,836 INFO L82 PathProgramCache]: Analyzing trace with hash 1293432562, now seen corresponding path program 1 times [2020-10-20 00:53:40,837 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:53:40,837 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [365587238] [2020-10-20 00:53:40,837 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:53:40,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:40,944 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:53:40,945 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [365587238] [2020-10-20 00:53:40,945 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2004395403] [2020-10-20 00:53:40,945 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:41,029 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:41,030 INFO L263 TraceCheckSpWp]: Trace formula consists of 237 conjuncts, 6 conjunts are in the unsatisfiable core [2020-10-20 00:53:41,033 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:53:41,083 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:53:41,084 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:53:41,084 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2020-10-20 00:53:41,084 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1411816901] [2020-10-20 00:53:41,085 INFO L461 AbstractCegarLoop]: Interpolant automaton has 10 states [2020-10-20 00:53:41,085 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:53:41,085 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2020-10-20 00:53:41,085 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2020-10-20 00:53:41,086 INFO L87 Difference]: Start difference. First operand 75 states and 98 transitions. Second operand 10 states. [2020-10-20 00:53:41,291 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:53:41,291 INFO L93 Difference]: Finished difference Result 206 states and 263 transitions. [2020-10-20 00:53:41,293 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2020-10-20 00:53:41,293 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 23 [2020-10-20 00:53:41,293 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:53:41,294 INFO L225 Difference]: With dead ends: 206 [2020-10-20 00:53:41,295 INFO L226 Difference]: Without dead ends: 146 [2020-10-20 00:53:41,295 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=42, Invalid=90, Unknown=0, NotChecked=0, Total=132 [2020-10-20 00:53:41,296 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2020-10-20 00:53:41,316 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 92. [2020-10-20 00:53:41,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 92 states. [2020-10-20 00:53:41,320 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 119 transitions. [2020-10-20 00:53:41,320 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 119 transitions. Word has length 23 [2020-10-20 00:53:41,320 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:53:41,320 INFO L481 AbstractCegarLoop]: Abstraction has 92 states and 119 transitions. [2020-10-20 00:53:41,320 INFO L482 AbstractCegarLoop]: Interpolant automaton has 10 states. [2020-10-20 00:53:41,321 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 119 transitions. [2020-10-20 00:53:41,322 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2020-10-20 00:53:41,322 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:53:41,322 INFO L422 BasicCegarLoop]: 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] [2020-10-20 00:53:41,538 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:41,539 INFO L429 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:53:41,539 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:53:41,540 INFO L82 PathProgramCache]: Analyzing trace with hash 1741027445, now seen corresponding path program 1 times [2020-10-20 00:53:41,540 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:53:41,541 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1912112296] [2020-10-20 00:53:41,541 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:53:41,602 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:41,959 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:53:41,959 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1912112296] [2020-10-20 00:53:41,960 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1878111825] [2020-10-20 00:53:41,960 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:42,039 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:42,042 INFO L263 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 22 conjunts are in the unsatisfiable core [2020-10-20 00:53:42,044 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:53:42,067 INFO L350 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:53:42,068 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 31 treesize of output 35 [2020-10-20 00:53:42,069 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:53:42,083 INFO L625 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:53:42,086 INFO L545 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:53:42,086 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:39, output treesize:18 [2020-10-20 00:53:42,111 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2020-10-20 00:53:42,112 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:53:42,120 INFO L625 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:53:42,120 INFO L545 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:53:42,121 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:26, output treesize:22 [2020-10-20 00:53:42,234 INFO L350 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:53:42,234 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 59 [2020-10-20 00:53:42,236 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:53:42,262 INFO L625 ElimStorePlain]: treesize reduction 24, result has 60.7 percent of original size [2020-10-20 00:53:42,268 INFO L545 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2020-10-20 00:53:42,268 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:41, output treesize:37 [2020-10-20 00:53:42,524 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:42,526 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:42,569 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:53:42,569 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:53:42,570 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2020-10-20 00:53:42,570 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1843222750] [2020-10-20 00:53:42,570 INFO L461 AbstractCegarLoop]: Interpolant automaton has 16 states [2020-10-20 00:53:42,571 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:53:42,571 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2020-10-20 00:53:42,571 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2020-10-20 00:53:42,572 INFO L87 Difference]: Start difference. First operand 92 states and 119 transitions. Second operand 16 states. [2020-10-20 00:53:44,932 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:53:44,932 INFO L93 Difference]: Finished difference Result 252 states and 308 transitions. [2020-10-20 00:53:44,933 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2020-10-20 00:53:44,933 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 25 [2020-10-20 00:53:44,933 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:53:44,938 INFO L225 Difference]: With dead ends: 252 [2020-10-20 00:53:44,939 INFO L226 Difference]: Without dead ends: 230 [2020-10-20 00:53:44,940 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 522 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=486, Invalid=1676, Unknown=0, NotChecked=0, Total=2162 [2020-10-20 00:53:44,943 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 230 states. [2020-10-20 00:53:44,964 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 230 to 96. [2020-10-20 00:53:44,965 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 96 states. [2020-10-20 00:53:44,966 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 126 transitions. [2020-10-20 00:53:44,966 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 126 transitions. Word has length 25 [2020-10-20 00:53:44,966 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:53:44,966 INFO L481 AbstractCegarLoop]: Abstraction has 96 states and 126 transitions. [2020-10-20 00:53:44,967 INFO L482 AbstractCegarLoop]: Interpolant automaton has 16 states. [2020-10-20 00:53:44,967 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 126 transitions. [2020-10-20 00:53:44,968 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2020-10-20 00:53:44,968 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:53:44,969 INFO L422 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:53:45,182 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2020-10-20 00:53:45,183 INFO L429 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:53:45,184 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:53:45,184 INFO L82 PathProgramCache]: Analyzing trace with hash -858936254, now seen corresponding path program 2 times [2020-10-20 00:53:45,184 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:53:45,185 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1972495610] [2020-10-20 00:53:45,185 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:53:45,205 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:45,321 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2020-10-20 00:53:45,322 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1972495610] [2020-10-20 00:53:45,322 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1386378968] [2020-10-20 00:53:45,322 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:45,386 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-10-20 00:53:45,387 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-10-20 00:53:45,395 INFO L263 TraceCheckSpWp]: Trace formula consists of 237 conjuncts, 11 conjunts are in the unsatisfiable core [2020-10-20 00:53:45,397 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:53:45,410 INFO L384 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 [2020-10-20 00:53:45,410 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:53:45,414 INFO L625 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:53:45,414 INFO L545 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:53:45,415 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:19, output treesize:15 [2020-10-20 00:53:45,468 INFO L350 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:53:45,469 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 23 treesize of output 46 [2020-10-20 00:53:45,470 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:53:45,488 INFO L625 ElimStorePlain]: treesize reduction 24, result has 47.8 percent of original size [2020-10-20 00:53:45,489 INFO L545 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:53:45,490 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:26, output treesize:7 [2020-10-20 00:53:45,523 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:45,525 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:45,541 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2020-10-20 00:53:45,542 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:53:45,542 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 13 [2020-10-20 00:53:45,542 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [918108140] [2020-10-20 00:53:45,543 INFO L461 AbstractCegarLoop]: Interpolant automaton has 13 states [2020-10-20 00:53:45,543 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:53:45,543 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2020-10-20 00:53:45,543 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2020-10-20 00:53:45,544 INFO L87 Difference]: Start difference. First operand 96 states and 126 transitions. Second operand 13 states. [2020-10-20 00:53:45,912 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:53:45,913 INFO L93 Difference]: Finished difference Result 170 states and 216 transitions. [2020-10-20 00:53:45,913 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2020-10-20 00:53:45,914 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 25 [2020-10-20 00:53:45,914 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:53:45,915 INFO L225 Difference]: With dead ends: 170 [2020-10-20 00:53:45,915 INFO L226 Difference]: Without dead ends: 168 [2020-10-20 00:53:45,916 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 20 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=85, Invalid=257, Unknown=0, NotChecked=0, Total=342 [2020-10-20 00:53:45,916 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states. [2020-10-20 00:53:45,928 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 106. [2020-10-20 00:53:45,929 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 106 states. [2020-10-20 00:53:45,929 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 141 transitions. [2020-10-20 00:53:45,930 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 141 transitions. Word has length 25 [2020-10-20 00:53:45,930 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:53:45,930 INFO L481 AbstractCegarLoop]: Abstraction has 106 states and 141 transitions. [2020-10-20 00:53:45,930 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2020-10-20 00:53:45,930 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 141 transitions. [2020-10-20 00:53:45,931 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2020-10-20 00:53:45,932 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:53:45,932 INFO L422 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:53:46,147 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:46,148 INFO L429 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:53:46,148 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:53:46,149 INFO L82 PathProgramCache]: Analyzing trace with hash -1096380170, now seen corresponding path program 2 times [2020-10-20 00:53:46,149 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:53:46,150 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [464244367] [2020-10-20 00:53:46,150 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:53:46,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:46,225 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 1 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:53:46,225 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [464244367] [2020-10-20 00:53:46,226 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [476668980] [2020-10-20 00:53:46,226 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:46,302 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-10-20 00:53:46,302 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-10-20 00:53:46,304 INFO L263 TraceCheckSpWp]: Trace formula consists of 270 conjuncts, 6 conjunts are in the unsatisfiable core [2020-10-20 00:53:46,306 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:53:46,353 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:53:46,354 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:53:46,354 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2020-10-20 00:53:46,355 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [12270584] [2020-10-20 00:53:46,355 INFO L461 AbstractCegarLoop]: Interpolant automaton has 10 states [2020-10-20 00:53:46,355 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:53:46,355 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2020-10-20 00:53:46,356 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2020-10-20 00:53:46,356 INFO L87 Difference]: Start difference. First operand 106 states and 141 transitions. Second operand 10 states. [2020-10-20 00:53:46,603 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:53:46,603 INFO L93 Difference]: Finished difference Result 216 states and 272 transitions. [2020-10-20 00:53:46,604 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2020-10-20 00:53:46,604 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 28 [2020-10-20 00:53:46,604 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:53:46,605 INFO L225 Difference]: With dead ends: 216 [2020-10-20 00:53:46,605 INFO L226 Difference]: Without dead ends: 203 [2020-10-20 00:53:46,609 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=79, Invalid=193, Unknown=0, NotChecked=0, Total=272 [2020-10-20 00:53:46,609 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2020-10-20 00:53:46,639 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 148. [2020-10-20 00:53:46,639 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 148 states. [2020-10-20 00:53:46,640 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 196 transitions. [2020-10-20 00:53:46,640 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 196 transitions. Word has length 28 [2020-10-20 00:53:46,641 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:53:46,641 INFO L481 AbstractCegarLoop]: Abstraction has 148 states and 196 transitions. [2020-10-20 00:53:46,641 INFO L482 AbstractCegarLoop]: Interpolant automaton has 10 states. [2020-10-20 00:53:46,641 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 196 transitions. [2020-10-20 00:53:46,645 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2020-10-20 00:53:46,646 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:53:46,646 INFO L422 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:53:46,847 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:46,847 INFO L429 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:53:46,848 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:53:46,848 INFO L82 PathProgramCache]: Analyzing trace with hash 219879636, now seen corresponding path program 2 times [2020-10-20 00:53:46,849 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:53:46,849 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1653406506] [2020-10-20 00:53:46,849 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:53:46,859 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:46,895 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2020-10-20 00:53:46,895 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1653406506] [2020-10-20 00:53:46,896 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [536886045] [2020-10-20 00:53:46,896 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:46,978 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-10-20 00:53:46,978 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-10-20 00:53:46,980 INFO L263 TraceCheckSpWp]: Trace formula consists of 249 conjuncts, 4 conjunts are in the unsatisfiable core [2020-10-20 00:53:46,982 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:53:47,003 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2020-10-20 00:53:47,003 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2020-10-20 00:53:47,003 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 6 [2020-10-20 00:53:47,003 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1568511566] [2020-10-20 00:53:47,004 INFO L461 AbstractCegarLoop]: Interpolant automaton has 4 states [2020-10-20 00:53:47,004 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:53:47,004 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2020-10-20 00:53:47,004 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2020-10-20 00:53:47,004 INFO L87 Difference]: Start difference. First operand 148 states and 196 transitions. Second operand 4 states. [2020-10-20 00:53:47,083 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:53:47,083 INFO L93 Difference]: Finished difference Result 246 states and 322 transitions. [2020-10-20 00:53:47,083 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2020-10-20 00:53:47,083 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 29 [2020-10-20 00:53:47,084 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:53:47,085 INFO L225 Difference]: With dead ends: 246 [2020-10-20 00:53:47,085 INFO L226 Difference]: Without dead ends: 129 [2020-10-20 00:53:47,086 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2020-10-20 00:53:47,087 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2020-10-20 00:53:47,096 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 114. [2020-10-20 00:53:47,097 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 114 states. [2020-10-20 00:53:47,097 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 145 transitions. [2020-10-20 00:53:47,097 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 145 transitions. Word has length 29 [2020-10-20 00:53:47,098 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:53:47,098 INFO L481 AbstractCegarLoop]: Abstraction has 114 states and 145 transitions. [2020-10-20 00:53:47,098 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2020-10-20 00:53:47,098 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 145 transitions. [2020-10-20 00:53:47,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2020-10-20 00:53:47,099 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:53:47,099 INFO L422 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:53:47,313 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2020-10-20 00:53:47,314 INFO L429 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:53:47,314 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:53:47,315 INFO L82 PathProgramCache]: Analyzing trace with hash 642581462, now seen corresponding path program 1 times [2020-10-20 00:53:47,315 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:53:47,315 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [374552309] [2020-10-20 00:53:47,316 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:53:47,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:47,532 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2020-10-20 00:53:47,532 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [374552309] [2020-10-20 00:53:47,533 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1899602578] [2020-10-20 00:53:47,533 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:47,592 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:47,594 INFO L263 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 14 conjunts are in the unsatisfiable core [2020-10-20 00:53:47,596 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:53:47,633 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2020-10-20 00:53:47,633 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:53:47,639 INFO L625 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:53:47,639 INFO L545 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:53:47,640 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:17, output treesize:9 [2020-10-20 00:53:47,689 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:47,690 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:47,736 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2020-10-20 00:53:47,736 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:53:47,736 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2020-10-20 00:53:47,737 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [200431831] [2020-10-20 00:53:47,737 INFO L461 AbstractCegarLoop]: Interpolant automaton has 15 states [2020-10-20 00:53:47,738 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:53:47,738 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2020-10-20 00:53:47,738 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2020-10-20 00:53:47,738 INFO L87 Difference]: Start difference. First operand 114 states and 145 transitions. Second operand 15 states. [2020-10-20 00:53:48,254 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:53:48,255 INFO L93 Difference]: Finished difference Result 183 states and 226 transitions. [2020-10-20 00:53:48,255 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2020-10-20 00:53:48,255 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 29 [2020-10-20 00:53:48,255 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:53:48,256 INFO L225 Difference]: With dead ends: 183 [2020-10-20 00:53:48,257 INFO L226 Difference]: Without dead ends: 181 [2020-10-20 00:53:48,258 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 122 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=150, Invalid=500, Unknown=0, NotChecked=0, Total=650 [2020-10-20 00:53:48,258 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 181 states. [2020-10-20 00:53:48,276 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 181 to 118. [2020-10-20 00:53:48,276 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 118 states. [2020-10-20 00:53:48,276 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 149 transitions. [2020-10-20 00:53:48,277 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 149 transitions. Word has length 29 [2020-10-20 00:53:48,277 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:53:48,277 INFO L481 AbstractCegarLoop]: Abstraction has 118 states and 149 transitions. [2020-10-20 00:53:48,277 INFO L482 AbstractCegarLoop]: Interpolant automaton has 15 states. [2020-10-20 00:53:48,277 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 149 transitions. [2020-10-20 00:53:48,278 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2020-10-20 00:53:48,278 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:53:48,278 INFO L422 BasicCegarLoop]: trace histogram [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] [2020-10-20 00:53:48,492 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:48,493 INFO L429 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:53:48,493 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:53:48,494 INFO L82 PathProgramCache]: Analyzing trace with hash -1240772930, now seen corresponding path program 3 times [2020-10-20 00:53:48,494 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:53:48,495 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1438816328] [2020-10-20 00:53:48,495 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:53:48,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:53:49,157 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2020-10-20 00:53:49,158 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1438816328] [2020-10-20 00:53:49,158 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [417910532] [2020-10-20 00:53:49,159 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:53:49,390 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2020-10-20 00:53:49,390 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-10-20 00:53:49,393 INFO L263 TraceCheckSpWp]: Trace formula consists of 284 conjuncts, 48 conjunts are in the unsatisfiable core [2020-10-20 00:53:49,396 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:53:49,404 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:53:49,421 INFO L350 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:53:49,422 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 36 treesize of output 54 [2020-10-20 00:53:49,423 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:53:49,450 INFO L625 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:53:49,451 INFO L545 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:53:49,451 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:78, output treesize:53 [2020-10-20 00:53:49,500 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:53:49,501 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:53:49,516 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:53:49,521 INFO L350 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:53:49,522 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 5 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 44 treesize of output 60 [2020-10-20 00:53:49,523 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:53:49,565 INFO L625 ElimStorePlain]: treesize reduction 20, result has 72.6 percent of original size [2020-10-20 00:53:49,565 INFO L545 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:53:49,566 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:61, output treesize:53 [2020-10-20 00:53:49,739 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:53:49,740 INFO L173 IndexEqualityManager]: detected equality via solver [2020-10-20 00:53:49,742 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:53:49,743 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:53:49,985 WARN L193 SmtUtils]: Spent 240.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 74 [2020-10-20 00:53:49,988 INFO L350 Elim1Store]: treesize reduction 16, result has 93.7 percent of original size [2020-10-20 00:53:49,989 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 4 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 19 case distinctions, treesize of input 66 treesize of output 275 [2020-10-20 00:53:49,990 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:49,993 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 6 disjuncts [2020-10-20 00:53:49,995 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 5 disjuncts [2020-10-20 00:53:49,997 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 4 disjuncts [2020-10-20 00:53:49,998 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-10-20 00:53:50,000 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:53:50,100 INFO L625 ElimStorePlain]: treesize reduction 207, result has 26.3 percent of original size [2020-10-20 00:53:50,102 INFO L545 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2020-10-20 00:53:50,102 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:82, output treesize:74 [2020-10-20 00:53:50,342 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:53:50,571 WARN L193 SmtUtils]: Spent 228.00 ms on a formula simplification that was a NOOP. DAG size: 118 [2020-10-20 00:53:50,572 INFO L350 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:53:50,572 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 5 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 25 case distinctions, treesize of input 80 treesize of output 429 [2020-10-20 00:53:50,577 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 7 disjuncts [2020-10-20 00:53:50,578 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 6 disjuncts [2020-10-20 00:53:50,579 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 5 disjuncts [2020-10-20 00:53:50,580 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 4 disjuncts [2020-10-20 00:53:50,581 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 3 disjuncts [2020-10-20 00:53:50,582 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:50,594 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 4 disjuncts [2020-10-20 00:53:50,596 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 3 disjuncts [2020-10-20 00:53:50,597 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-10-20 00:53:50,606 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 2 disjuncts [2020-10-20 00:53:50,614 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-10-20 00:53:50,616 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 3 disjuncts [2020-10-20 00:53:50,617 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:50,622 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 3 disjuncts [2020-10-20 00:53:50,623 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 3 disjuncts [2020-10-20 00:53:50,624 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:50,625 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 2 disjuncts [2020-10-20 00:53:50,626 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:50,627 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:50,630 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:50,632 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-10-20 00:53:50,634 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 2 disjuncts [2020-10-20 00:53:50,637 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 7 disjuncts [2020-10-20 00:53:50,638 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 7 disjuncts [2020-10-20 00:53:50,640 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 6 disjuncts [2020-10-20 00:53:50,642 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 5 disjuncts [2020-10-20 00:53:50,643 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 5 disjuncts [2020-10-20 00:53:50,644 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 5 disjuncts [2020-10-20 00:53:50,645 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 5 disjuncts [2020-10-20 00:53:50,646 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 5 disjuncts [2020-10-20 00:53:50,647 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 4 disjuncts [2020-10-20 00:53:50,648 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 6 disjuncts [2020-10-20 00:53:50,650 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 5 disjuncts [2020-10-20 00:53:50,652 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 4 disjuncts [2020-10-20 00:53:50,655 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 6 disjuncts [2020-10-20 00:53:50,657 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 5 disjuncts [2020-10-20 00:53:50,659 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 3 disjuncts [2020-10-20 00:53:50,670 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 5 disjuncts [2020-10-20 00:53:50,671 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 4 disjuncts [2020-10-20 00:53:50,672 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 3 disjuncts [2020-10-20 00:53:50,675 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 5 disjuncts [2020-10-20 00:53:50,676 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 4 disjuncts [2020-10-20 00:53:50,677 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 3 disjuncts [2020-10-20 00:53:50,680 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 5 disjuncts [2020-10-20 00:53:50,681 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 4 disjuncts [2020-10-20 00:53:50,682 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 3 disjuncts [2020-10-20 00:53:50,687 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 7 disjuncts [2020-10-20 00:53:50,689 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 6 disjuncts [2020-10-20 00:53:50,690 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 6 disjuncts [2020-10-20 00:53:50,691 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 5 disjuncts [2020-10-20 00:53:50,693 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 4 disjuncts [2020-10-20 00:53:50,694 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 4 disjuncts [2020-10-20 00:53:50,695 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 3 disjuncts [2020-10-20 00:53:50,698 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 4 disjuncts [2020-10-20 00:53:50,699 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 4 disjuncts [2020-10-20 00:53:50,701 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 3 disjuncts [2020-10-20 00:53:50,704 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 4 disjuncts [2020-10-20 00:53:50,705 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 6 disjuncts [2020-10-20 00:53:50,706 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 5 disjuncts [2020-10-20 00:53:50,707 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 4 disjuncts [2020-10-20 00:53:50,710 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 3 disjuncts [2020-10-20 00:53:50,714 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 6 disjuncts [2020-10-20 00:53:50,715 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 5 disjuncts [2020-10-20 00:53:50,716 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 4 disjuncts [2020-10-20 00:53:50,717 INFO L603 QuantifierPusher]: Distributing 3 conjuncts over 3 disjuncts [2020-10-20 00:53:50,725 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:53:51,253 WARN L193 SmtUtils]: Spent 527.00 ms on a formula simplification. DAG size of input: 179 DAG size of output: 49 [2020-10-20 00:53:51,254 INFO L625 ElimStorePlain]: treesize reduction 2482, result has 3.7 percent of original size [2020-10-20 00:53:51,257 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-10-20 00:53:51,260 INFO L545 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 1 xjuncts. [2020-10-20 00:53:51,261 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:93, output treesize:95 [2020-10-20 00:53:51,262 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-10-20 00:53:51,338 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-10-20 00:53:51,341 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-10-20 00:53:51,342 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-10-20 00:53:51,644 WARN L193 SmtUtils]: Spent 132.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 59 [2020-10-20 00:53:51,652 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:52,360 INFO L375 QuantifierPusher]: Applying distributivity to a CONJUNCTION[2, 2, 5, 1] term [2020-10-20 00:53:52,361 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:52,526 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:52,898 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:52,900 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:53:52,907 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 4 disjuncts [2020-10-20 00:53:52,984 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-10-20 00:53:52,985 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:53:52,985 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 18] total 28 [2020-10-20 00:53:52,985 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2146982331] [2020-10-20 00:53:52,986 INFO L461 AbstractCegarLoop]: Interpolant automaton has 28 states [2020-10-20 00:53:52,986 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:53:52,986 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2020-10-20 00:53:52,986 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=666, Unknown=0, NotChecked=0, Total=756 [2020-10-20 00:53:52,987 INFO L87 Difference]: Start difference. First operand 118 states and 149 transitions. Second operand 28 states. [2020-10-20 00:53:56,068 WARN L193 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 47 [2020-10-20 00:53:56,969 WARN L193 SmtUtils]: Spent 139.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 67 [2020-10-20 00:53:57,463 WARN L193 SmtUtils]: Spent 191.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 69 [2020-10-20 00:53:58,109 WARN L193 SmtUtils]: Spent 397.00 ms on a formula simplification. DAG size of input: 128 DAG size of output: 73 [2020-10-20 00:54:00,517 WARN L193 SmtUtils]: Spent 2.25 s on a formula simplification. DAG size of input: 93 DAG size of output: 67 [2020-10-20 00:54:01,088 WARN L193 SmtUtils]: Spent 354.00 ms on a formula simplification. DAG size of input: 128 DAG size of output: 74 [2020-10-20 00:54:03,400 WARN L193 SmtUtils]: Spent 552.00 ms on a formula simplification. DAG size of input: 130 DAG size of output: 75 [2020-10-20 00:54:03,733 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:54:03,734 INFO L93 Difference]: Finished difference Result 186 states and 228 transitions. [2020-10-20 00:54:03,734 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2020-10-20 00:54:03,734 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 31 [2020-10-20 00:54:03,734 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:54:03,736 INFO L225 Difference]: With dead ends: 186 [2020-10-20 00:54:03,736 INFO L226 Difference]: Without dead ends: 141 [2020-10-20 00:54:03,737 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 495 ImplicationChecksByTransitivity, 11.1s TimeCoverageRelationStatistics Valid=462, Invalid=2087, Unknown=1, NotChecked=0, Total=2550 [2020-10-20 00:54:03,738 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 141 states. [2020-10-20 00:54:03,751 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 141 to 121. [2020-10-20 00:54:03,751 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 121 states. [2020-10-20 00:54:03,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 153 transitions. [2020-10-20 00:54:03,752 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 153 transitions. Word has length 31 [2020-10-20 00:54:03,752 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:54:03,752 INFO L481 AbstractCegarLoop]: Abstraction has 121 states and 153 transitions. [2020-10-20 00:54:03,752 INFO L482 AbstractCegarLoop]: Interpolant automaton has 28 states. [2020-10-20 00:54:03,753 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 153 transitions. [2020-10-20 00:54:03,753 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2020-10-20 00:54:03,753 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:54:03,754 INFO L422 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:54:03,966 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,11 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:54:03,967 INFO L429 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:54:03,967 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:54:03,968 INFO L82 PathProgramCache]: Analyzing trace with hash -956621735, now seen corresponding path program 1 times [2020-10-20 00:54:03,968 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:54:03,968 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1497875827] [2020-10-20 00:54:03,969 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:54:03,981 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:54:04,008 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2020-10-20 00:54:04,009 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1497875827] [2020-10-20 00:54:04,009 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2020-10-20 00:54:04,009 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2020-10-20 00:54:04,009 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [918802194] [2020-10-20 00:54:04,010 INFO L461 AbstractCegarLoop]: Interpolant automaton has 5 states [2020-10-20 00:54:04,010 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:54:04,010 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2020-10-20 00:54:04,010 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2020-10-20 00:54:04,011 INFO L87 Difference]: Start difference. First operand 121 states and 153 transitions. Second operand 5 states. [2020-10-20 00:54:04,055 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:54:04,055 INFO L93 Difference]: Finished difference Result 197 states and 246 transitions. [2020-10-20 00:54:04,056 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2020-10-20 00:54:04,056 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 31 [2020-10-20 00:54:04,057 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:54:04,058 INFO L225 Difference]: With dead ends: 197 [2020-10-20 00:54:04,059 INFO L226 Difference]: Without dead ends: 141 [2020-10-20 00:54:04,060 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2020-10-20 00:54:04,061 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 141 states. [2020-10-20 00:54:04,073 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 141 to 121. [2020-10-20 00:54:04,074 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 121 states. [2020-10-20 00:54:04,074 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 152 transitions. [2020-10-20 00:54:04,075 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 152 transitions. Word has length 31 [2020-10-20 00:54:04,075 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:54:04,075 INFO L481 AbstractCegarLoop]: Abstraction has 121 states and 152 transitions. [2020-10-20 00:54:04,075 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2020-10-20 00:54:04,075 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 152 transitions. [2020-10-20 00:54:04,076 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2020-10-20 00:54:04,076 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:54:04,076 INFO L422 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:54:04,077 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12 [2020-10-20 00:54:04,077 INFO L429 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:54:04,077 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:54:04,077 INFO L82 PathProgramCache]: Analyzing trace with hash 2054058346, now seen corresponding path program 2 times [2020-10-20 00:54:04,078 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:54:04,078 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [830044652] [2020-10-20 00:54:04,078 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:54:04,097 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:54:04,168 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 3 proven. 10 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2020-10-20 00:54:04,169 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [830044652] [2020-10-20 00:54:04,169 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1289890051] [2020-10-20 00:54:04,169 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:54:04,243 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-10-20 00:54:04,244 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-10-20 00:54:04,245 INFO L263 TraceCheckSpWp]: Trace formula consists of 259 conjuncts, 8 conjunts are in the unsatisfiable core [2020-10-20 00:54:04,248 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:54:04,311 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2020-10-20 00:54:04,312 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:54:04,312 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 13 [2020-10-20 00:54:04,312 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [672322736] [2020-10-20 00:54:04,313 INFO L461 AbstractCegarLoop]: Interpolant automaton has 13 states [2020-10-20 00:54:04,313 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:54:04,313 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2020-10-20 00:54:04,313 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=111, Unknown=0, NotChecked=0, Total=156 [2020-10-20 00:54:04,314 INFO L87 Difference]: Start difference. First operand 121 states and 152 transitions. Second operand 13 states. [2020-10-20 00:54:04,622 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:54:04,622 INFO L93 Difference]: Finished difference Result 403 states and 505 transitions. [2020-10-20 00:54:04,623 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2020-10-20 00:54:04,623 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 33 [2020-10-20 00:54:04,623 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:54:04,625 INFO L225 Difference]: With dead ends: 403 [2020-10-20 00:54:04,625 INFO L226 Difference]: Without dead ends: 298 [2020-10-20 00:54:04,626 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=99, Invalid=243, Unknown=0, NotChecked=0, Total=342 [2020-10-20 00:54:04,626 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 298 states. [2020-10-20 00:54:04,645 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 298 to 204. [2020-10-20 00:54:04,645 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 204 states. [2020-10-20 00:54:04,646 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 204 states to 204 states and 261 transitions. [2020-10-20 00:54:04,646 INFO L78 Accepts]: Start accepts. Automaton has 204 states and 261 transitions. Word has length 33 [2020-10-20 00:54:04,646 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:54:04,646 INFO L481 AbstractCegarLoop]: Abstraction has 204 states and 261 transitions. [2020-10-20 00:54:04,647 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2020-10-20 00:54:04,647 INFO L276 IsEmpty]: Start isEmpty. Operand 204 states and 261 transitions. [2020-10-20 00:54:04,647 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2020-10-20 00:54:04,647 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:54:04,648 INFO L422 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:54:04,856 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2020-10-20 00:54:04,857 INFO L429 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:54:04,857 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:54:04,857 INFO L82 PathProgramCache]: Analyzing trace with hash -1071791489, now seen corresponding path program 4 times [2020-10-20 00:54:04,858 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:54:04,858 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1115748788] [2020-10-20 00:54:04,858 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:54:04,873 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:54:04,928 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 2 proven. 16 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:54:04,929 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1115748788] [2020-10-20 00:54:04,929 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [834157085] [2020-10-20 00:54:04,929 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:54:04,973 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2020-10-20 00:54:04,973 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-10-20 00:54:04,974 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 8 conjunts are in the unsatisfiable core [2020-10-20 00:54:04,975 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:54:05,041 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 6 proven. 12 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:54:05,041 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:54:05,041 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 13 [2020-10-20 00:54:05,042 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2052329916] [2020-10-20 00:54:05,042 INFO L461 AbstractCegarLoop]: Interpolant automaton has 13 states [2020-10-20 00:54:05,042 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:54:05,043 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2020-10-20 00:54:05,043 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=111, Unknown=0, NotChecked=0, Total=156 [2020-10-20 00:54:05,043 INFO L87 Difference]: Start difference. First operand 204 states and 261 transitions. Second operand 13 states. [2020-10-20 00:54:05,450 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:54:05,451 INFO L93 Difference]: Finished difference Result 487 states and 611 transitions. [2020-10-20 00:54:05,451 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2020-10-20 00:54:05,451 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 34 [2020-10-20 00:54:05,452 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:54:05,454 INFO L225 Difference]: With dead ends: 487 [2020-10-20 00:54:05,454 INFO L226 Difference]: Without dead ends: 465 [2020-10-20 00:54:05,455 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 90 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=138, Invalid=368, Unknown=0, NotChecked=0, Total=506 [2020-10-20 00:54:05,456 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 465 states. [2020-10-20 00:54:05,483 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 465 to 289. [2020-10-20 00:54:05,483 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 289 states. [2020-10-20 00:54:05,484 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 289 states to 289 states and 379 transitions. [2020-10-20 00:54:05,485 INFO L78 Accepts]: Start accepts. Automaton has 289 states and 379 transitions. Word has length 34 [2020-10-20 00:54:05,485 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:54:05,485 INFO L481 AbstractCegarLoop]: Abstraction has 289 states and 379 transitions. [2020-10-20 00:54:05,485 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2020-10-20 00:54:05,485 INFO L276 IsEmpty]: Start isEmpty. Operand 289 states and 379 transitions. [2020-10-20 00:54:05,486 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2020-10-20 00:54:05,486 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:54:05,486 INFO L422 BasicCegarLoop]: trace histogram [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] [2020-10-20 00:54:05,699 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2020-10-20 00:54:05,700 INFO L429 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:54:05,700 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:54:05,701 INFO L82 PathProgramCache]: Analyzing trace with hash -715108188, now seen corresponding path program 2 times [2020-10-20 00:54:05,701 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:54:05,701 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1199867945] [2020-10-20 00:54:05,702 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:54:05,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:54:06,319 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 1 proven. 14 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2020-10-20 00:54:06,319 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1199867945] [2020-10-20 00:54:06,320 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [646117685] [2020-10-20 00:54:06,320 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:54:06,420 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-10-20 00:54:06,421 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-10-20 00:54:06,423 INFO L263 TraceCheckSpWp]: Trace formula consists of 281 conjuncts, 32 conjunts are in the unsatisfiable core [2020-10-20 00:54:06,425 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:54:06,448 INFO L350 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:54:06,449 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 31 treesize of output 35 [2020-10-20 00:54:06,450 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:06,469 INFO L625 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:54:06,471 INFO L545 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2020-10-20 00:54:06,471 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:57, output treesize:40 [2020-10-20 00:54:06,552 INFO L350 Elim1Store]: treesize reduction 12, result has 70.7 percent of original size [2020-10-20 00:54:06,552 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 41 treesize of output 74 [2020-10-20 00:54:06,554 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:06,592 INFO L625 ElimStorePlain]: treesize reduction 42, result has 54.8 percent of original size [2020-10-20 00:54:06,593 INFO L545 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2020-10-20 00:54:06,594 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:55, output treesize:51 [2020-10-20 00:54:06,746 INFO L350 Elim1Store]: treesize reduction 12, result has 83.3 percent of original size [2020-10-20 00:54:06,747 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 2 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 48 treesize of output 108 [2020-10-20 00:54:06,748 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:06,796 INFO L625 ElimStorePlain]: treesize reduction 72, result has 44.6 percent of original size [2020-10-20 00:54:06,798 INFO L545 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2020-10-20 00:54:06,799 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 5 variables, input treesize:62, output treesize:44 [2020-10-20 00:54:07,013 INFO L350 Elim1Store]: treesize reduction 12, result has 83.3 percent of original size [2020-10-20 00:54:07,016 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 2 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 55 treesize of output 111 [2020-10-20 00:54:07,018 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:07,076 INFO L625 ElimStorePlain]: treesize reduction 72, result has 46.3 percent of original size [2020-10-20 00:54:07,078 INFO L545 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 1 xjuncts. [2020-10-20 00:54:07,078 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:66, output treesize:62 [2020-10-20 00:54:07,413 INFO L350 Elim1Store]: treesize reduction 12, result has 90.8 percent of original size [2020-10-20 00:54:07,413 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 2 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 6 case distinctions, treesize of input 75 treesize of output 178 [2020-10-20 00:54:07,415 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:07,502 INFO L625 ElimStorePlain]: treesize reduction 110, result has 41.2 percent of original size [2020-10-20 00:54:07,504 INFO L545 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-2 vars, End of recursive call: 5 dim-0 vars, and 1 xjuncts. [2020-10-20 00:54:07,504 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 6 variables, input treesize:83, output treesize:77 [2020-10-20 00:54:07,713 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:54:07,714 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:54:07,722 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-10-20 00:54:07,890 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 3 proven. 14 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:54:07,891 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:54:07,891 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 14] total 24 [2020-10-20 00:54:07,891 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [611865612] [2020-10-20 00:54:07,892 INFO L461 AbstractCegarLoop]: Interpolant automaton has 24 states [2020-10-20 00:54:07,892 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:54:07,892 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2020-10-20 00:54:07,892 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=479, Unknown=0, NotChecked=0, Total=552 [2020-10-20 00:54:07,892 INFO L87 Difference]: Start difference. First operand 289 states and 379 transitions. Second operand 24 states. [2020-10-20 00:54:12,218 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:54:12,219 INFO L93 Difference]: Finished difference Result 559 states and 708 transitions. [2020-10-20 00:54:12,220 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2020-10-20 00:54:12,220 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 34 [2020-10-20 00:54:12,220 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:54:12,222 INFO L225 Difference]: With dead ends: 559 [2020-10-20 00:54:12,223 INFO L226 Difference]: Without dead ends: 557 [2020-10-20 00:54:12,224 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 23 SyntacticMatches, 2 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 773 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=629, Invalid=2677, Unknown=0, NotChecked=0, Total=3306 [2020-10-20 00:54:12,225 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 557 states. [2020-10-20 00:54:12,271 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 557 to 387. [2020-10-20 00:54:12,271 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 387 states. [2020-10-20 00:54:12,272 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 387 states to 387 states and 513 transitions. [2020-10-20 00:54:12,273 INFO L78 Accepts]: Start accepts. Automaton has 387 states and 513 transitions. Word has length 34 [2020-10-20 00:54:12,273 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:54:12,273 INFO L481 AbstractCegarLoop]: Abstraction has 387 states and 513 transitions. [2020-10-20 00:54:12,273 INFO L482 AbstractCegarLoop]: Interpolant automaton has 24 states. [2020-10-20 00:54:12,273 INFO L276 IsEmpty]: Start isEmpty. Operand 387 states and 513 transitions. [2020-10-20 00:54:12,274 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2020-10-20 00:54:12,274 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:54:12,275 INFO L422 BasicCegarLoop]: trace histogram [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] [2020-10-20 00:54:12,487 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2020-10-20 00:54:12,488 INFO L429 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:54:12,488 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:54:12,488 INFO L82 PathProgramCache]: Analyzing trace with hash 1136182421, now seen corresponding path program 5 times [2020-10-20 00:54:12,489 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:54:12,489 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [317885625] [2020-10-20 00:54:12,489 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:54:12,595 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:54:12,971 WARN L193 SmtUtils]: Spent 111.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 34 [2020-10-20 00:54:13,096 WARN L193 SmtUtils]: Spent 105.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 38 [2020-10-20 00:54:13,691 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2020-10-20 00:54:13,691 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [317885625] [2020-10-20 00:54:13,691 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2093135359] [2020-10-20 00:54:13,692 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:54:13,992 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2020-10-20 00:54:13,992 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-10-20 00:54:13,995 INFO L263 TraceCheckSpWp]: Trace formula consists of 313 conjuncts, 52 conjunts are in the unsatisfiable core [2020-10-20 00:54:13,998 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:54:14,014 INFO L350 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:54:14,015 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 31 treesize of output 35 [2020-10-20 00:54:14,016 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:54:14,017 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:54:14,018 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:14,063 INFO L625 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:54:14,064 INFO L545 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:54:14,064 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:100, output treesize:95 [2020-10-20 00:54:14,158 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,160 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,161 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,162 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,163 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,164 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,171 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,173 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,174 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,177 INFO L350 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:54:14,177 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 14 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 3 case distinctions, treesize of input 71 treesize of output 88 [2020-10-20 00:54:14,178 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:14,226 INFO L625 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:54:14,227 INFO L545 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:54:14,227 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:103, output treesize:99 [2020-10-20 00:54:14,547 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,550 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,551 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,552 INFO L173 IndexEqualityManager]: detected equality via solver [2020-10-20 00:54:14,553 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,557 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,566 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,567 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:14,638 INFO L350 Elim1Store]: treesize reduction 8, result has 91.6 percent of original size [2020-10-20 00:54:14,639 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 12 select indices, 12 select index equivalence classes, 14 disjoint index pairs (out of 66 index pairs), introduced 11 new quantified variables, introduced 11 case distinctions, treesize of input 112 treesize of output 194 [2020-10-20 00:54:14,641 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-10-20 00:54:14,642 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:54:14,644 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:54:14,645 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-10-20 00:54:14,646 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:54:14,649 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:14,881 WARN L193 SmtUtils]: Spent 231.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 59 [2020-10-20 00:54:14,882 INFO L625 ElimStorePlain]: treesize reduction 115, result has 48.2 percent of original size [2020-10-20 00:54:14,884 INFO L545 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 1 xjuncts. [2020-10-20 00:54:14,886 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:141, output treesize:107 [2020-10-20 00:54:15,477 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:15,480 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:15,481 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:15,483 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:15,485 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:15,487 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:15,488 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:15,489 INFO L173 IndexEqualityManager]: detected equality via solver [2020-10-20 00:54:15,494 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:15,495 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:15,497 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:15,551 INFO L350 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:54:15,552 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 14 disjoint index pairs (out of 45 index pairs), introduced 9 new quantified variables, introduced 7 case distinctions, treesize of input 110 treesize of output 199 [2020-10-20 00:54:15,554 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:15,767 WARN L193 SmtUtils]: Spent 212.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 68 [2020-10-20 00:54:15,768 INFO L625 ElimStorePlain]: treesize reduction 68, result has 66.5 percent of original size [2020-10-20 00:54:15,770 INFO L545 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: 4 dim-0 vars, and 1 xjuncts. [2020-10-20 00:54:15,771 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 5 variables, input treesize:139, output treesize:135 [2020-10-20 00:54:16,250 INFO L350 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:54:16,250 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 9 select indices, 9 select index equivalence classes, 14 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 6 case distinctions, treesize of input 99 treesize of output 186 [2020-10-20 00:54:16,252 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:16,373 WARN L193 SmtUtils]: Spent 120.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 58 [2020-10-20 00:54:16,374 INFO L625 ElimStorePlain]: treesize reduction 68, result has 63.0 percent of original size [2020-10-20 00:54:16,379 INFO L545 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-2 vars, End of recursive call: 5 dim-0 vars, and 1 xjuncts. [2020-10-20 00:54:16,379 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 6 variables, input treesize:122, output treesize:116 [2020-10-20 00:54:16,929 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:54:16,931 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:54:16,941 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 6 disjuncts [2020-10-20 00:54:17,104 WARN L193 SmtUtils]: Spent 146.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 60 [2020-10-20 00:54:17,311 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2020-10-20 00:54:17,311 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:54:17,312 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 28 [2020-10-20 00:54:17,312 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2023689845] [2020-10-20 00:54:17,313 INFO L461 AbstractCegarLoop]: Interpolant automaton has 28 states [2020-10-20 00:54:17,313 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:54:17,313 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2020-10-20 00:54:17,314 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=667, Unknown=0, NotChecked=0, Total=756 [2020-10-20 00:54:17,314 INFO L87 Difference]: Start difference. First operand 387 states and 513 transitions. Second operand 28 states. [2020-10-20 00:54:17,528 WARN L193 SmtUtils]: Spent 103.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 58 [2020-10-20 00:54:17,734 WARN L193 SmtUtils]: Spent 118.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 59 [2020-10-20 00:54:17,918 WARN L193 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 57 [2020-10-20 00:54:18,147 WARN L193 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 61 [2020-10-20 00:54:18,417 WARN L193 SmtUtils]: Spent 190.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 88 [2020-10-20 00:54:18,674 WARN L193 SmtUtils]: Spent 159.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 69 [2020-10-20 00:54:18,894 WARN L193 SmtUtils]: Spent 134.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 63 [2020-10-20 00:54:19,165 WARN L193 SmtUtils]: Spent 167.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 71 [2020-10-20 00:54:19,367 WARN L193 SmtUtils]: Spent 148.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 67 [2020-10-20 00:54:19,656 WARN L193 SmtUtils]: Spent 181.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 75 [2020-10-20 00:54:19,850 WARN L193 SmtUtils]: Spent 142.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 64 [2020-10-20 00:54:24,182 WARN L193 SmtUtils]: Spent 198.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 75 [2020-10-20 00:54:24,475 WARN L193 SmtUtils]: Spent 168.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 74 [2020-10-20 00:54:25,188 WARN L193 SmtUtils]: Spent 142.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 68 [2020-10-20 00:54:25,512 WARN L193 SmtUtils]: Spent 175.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 90 [2020-10-20 00:54:25,976 WARN L193 SmtUtils]: Spent 308.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 98 [2020-10-20 00:54:26,590 WARN L193 SmtUtils]: Spent 219.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 94 [2020-10-20 00:54:26,835 WARN L193 SmtUtils]: Spent 138.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 86 [2020-10-20 00:54:27,051 WARN L193 SmtUtils]: Spent 129.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 64 [2020-10-20 00:54:27,673 WARN L193 SmtUtils]: Spent 170.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 91 [2020-10-20 00:54:28,283 WARN L193 SmtUtils]: Spent 211.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 92 [2020-10-20 00:54:28,525 WARN L193 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 62 [2020-10-20 00:54:29,435 WARN L193 SmtUtils]: Spent 179.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 93 [2020-10-20 00:54:30,020 WARN L193 SmtUtils]: Spent 145.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 89 [2020-10-20 00:54:30,720 WARN L193 SmtUtils]: Spent 176.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 91 [2020-10-20 00:54:31,174 WARN L193 SmtUtils]: Spent 175.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 93 [2020-10-20 00:54:31,351 WARN L193 SmtUtils]: Spent 124.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 61 [2020-10-20 00:54:31,362 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:54:31,362 INFO L93 Difference]: Finished difference Result 456 states and 592 transitions. [2020-10-20 00:54:31,362 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2020-10-20 00:54:31,362 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 37 [2020-10-20 00:54:31,363 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:54:31,364 INFO L225 Difference]: With dead ends: 456 [2020-10-20 00:54:31,365 INFO L226 Difference]: Without dead ends: 414 [2020-10-20 00:54:31,366 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 541 ImplicationChecksByTransitivity, 14.1s TimeCoverageRelationStatistics Valid=513, Invalid=2455, Unknown=2, NotChecked=0, Total=2970 [2020-10-20 00:54:31,367 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 414 states. [2020-10-20 00:54:31,413 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 414 to 390. [2020-10-20 00:54:31,413 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 390 states. [2020-10-20 00:54:31,415 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 390 states to 390 states and 517 transitions. [2020-10-20 00:54:31,415 INFO L78 Accepts]: Start accepts. Automaton has 390 states and 517 transitions. Word has length 37 [2020-10-20 00:54:31,415 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:54:31,416 INFO L481 AbstractCegarLoop]: Abstraction has 390 states and 517 transitions. [2020-10-20 00:54:31,416 INFO L482 AbstractCegarLoop]: Interpolant automaton has 28 states. [2020-10-20 00:54:31,416 INFO L276 IsEmpty]: Start isEmpty. Operand 390 states and 517 transitions. [2020-10-20 00:54:31,417 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2020-10-20 00:54:31,417 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:54:31,417 INFO L422 BasicCegarLoop]: trace histogram [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, 1] [2020-10-20 00:54:31,629 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:54:31,630 INFO L429 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:54:31,630 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:54:31,630 INFO L82 PathProgramCache]: Analyzing trace with hash -1571641544, now seen corresponding path program 1 times [2020-10-20 00:54:31,631 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:54:31,632 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [192090813] [2020-10-20 00:54:31,633 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:54:31,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:54:31,926 WARN L193 SmtUtils]: Spent 102.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 38 [2020-10-20 00:54:32,052 WARN L193 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 44 [2020-10-20 00:54:32,221 WARN L193 SmtUtils]: Spent 158.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 42 [2020-10-20 00:54:32,467 WARN L193 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 39 [2020-10-20 00:54:32,603 WARN L193 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 50 [2020-10-20 00:54:32,783 WARN L193 SmtUtils]: Spent 152.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 53 [2020-10-20 00:54:33,058 WARN L193 SmtUtils]: Spent 208.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 62 [2020-10-20 00:54:33,261 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 3 proven. 16 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-10-20 00:54:33,262 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [192090813] [2020-10-20 00:54:33,262 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [685357112] [2020-10-20 00:54:33,262 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-10-20 00:54:33,380 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-10-20 00:54:33,382 INFO L263 TraceCheckSpWp]: Trace formula consists of 292 conjuncts, 48 conjunts are in the unsatisfiable core [2020-10-20 00:54:33,386 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-10-20 00:54:33,397 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2020-10-20 00:54:33,402 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:33,422 INFO L625 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:54:33,423 INFO L545 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:54:33,423 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:57, output treesize:55 [2020-10-20 00:54:33,490 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:33,511 INFO L350 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:54:33,511 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 5 case distinctions, treesize of input 46 treesize of output 78 [2020-10-20 00:54:33,512 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:33,577 INFO L625 ElimStorePlain]: treesize reduction 28, result has 70.2 percent of original size [2020-10-20 00:54:33,577 INFO L545 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:54:33,577 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:70, output treesize:66 [2020-10-20 00:54:33,733 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:33,775 INFO L350 Elim1Store]: treesize reduction 20, result has 61.5 percent of original size [2020-10-20 00:54:33,775 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 4 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 6 case distinctions, treesize of input 51 treesize of output 86 [2020-10-20 00:54:33,778 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:33,839 INFO L625 ElimStorePlain]: treesize reduction 40, result has 63.0 percent of original size [2020-10-20 00:54:33,840 INFO L545 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:54:33,841 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:72, output treesize:59 [2020-10-20 00:54:34,058 INFO L190 IndexEqualityManager]: detected not equals via solver [2020-10-20 00:54:34,091 INFO L350 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2020-10-20 00:54:34,091 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 4 disjoint index pairs (out of 10 index pairs), introduced 6 new quantified variables, introduced 6 case distinctions, treesize of input 57 treesize of output 107 [2020-10-20 00:54:34,093 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:34,161 INFO L625 ElimStorePlain]: treesize reduction 80, result has 48.1 percent of original size [2020-10-20 00:54:34,162 INFO L545 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:54:34,162 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:78, output treesize:74 [2020-10-20 00:54:34,557 INFO L350 Elim1Store]: treesize reduction 8, result has 91.6 percent of original size [2020-10-20 00:54:34,558 INFO L384 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 4 disjoint index pairs (out of 21 index pairs), introduced 9 new quantified variables, introduced 10 case distinctions, treesize of input 106 treesize of output 162 [2020-10-20 00:54:34,560 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-10-20 00:54:34,561 INFO L603 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-10-20 00:54:34,567 INFO L545 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2020-10-20 00:54:34,575 INFO L625 ElimStorePlain]: treesize reduction 162, result has 0.6 percent of original size [2020-10-20 00:54:34,575 INFO L545 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2020-10-20 00:54:34,575 INFO L244 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:118, output treesize:1 [2020-10-20 00:54:34,588 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2020-10-20 00:54:34,588 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-10-20 00:54:34,588 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2020-10-20 00:54:34,588 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [960374372] [2020-10-20 00:54:34,589 INFO L461 AbstractCegarLoop]: Interpolant automaton has 23 states [2020-10-20 00:54:34,589 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-10-20 00:54:34,590 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2020-10-20 00:54:34,590 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=450, Unknown=0, NotChecked=0, Total=506 [2020-10-20 00:54:34,590 INFO L87 Difference]: Start difference. First operand 390 states and 517 transitions. Second operand 23 states. [2020-10-20 00:54:35,081 WARN L193 SmtUtils]: Spent 105.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 39 [2020-10-20 00:54:35,300 WARN L193 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 43 [2020-10-20 00:54:35,610 WARN L193 SmtUtils]: Spent 146.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 45 [2020-10-20 00:54:35,857 WARN L193 SmtUtils]: Spent 181.00 ms on a formula simplification. DAG size of input: 118 DAG size of output: 50 [2020-10-20 00:54:36,081 WARN L193 SmtUtils]: Spent 155.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 46 [2020-10-20 00:54:36,264 WARN L193 SmtUtils]: Spent 128.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 40 [2020-10-20 00:54:36,467 WARN L193 SmtUtils]: Spent 135.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 44 [2020-10-20 00:54:36,678 WARN L193 SmtUtils]: Spent 135.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 50 [2020-10-20 00:54:36,924 WARN L193 SmtUtils]: Spent 146.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 46 [2020-10-20 00:54:37,081 WARN L193 SmtUtils]: Spent 111.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 40 [2020-10-20 00:54:37,293 WARN L193 SmtUtils]: Spent 167.00 ms on a formula simplification. DAG size of input: 119 DAG size of output: 50 [2020-10-20 00:54:37,463 WARN L193 SmtUtils]: Spent 130.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 45 [2020-10-20 00:54:37,735 WARN L193 SmtUtils]: Spent 222.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 58 [2020-10-20 00:54:37,966 WARN L193 SmtUtils]: Spent 137.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 44 [2020-10-20 00:54:38,201 WARN L193 SmtUtils]: Spent 134.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 48 [2020-10-20 00:54:38,370 WARN L193 SmtUtils]: Spent 120.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 44 [2020-10-20 00:54:38,718 WARN L193 SmtUtils]: Spent 120.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 44 [2020-10-20 00:54:38,920 WARN L193 SmtUtils]: Spent 127.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 47 [2020-10-20 00:54:39,119 WARN L193 SmtUtils]: Spent 120.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 39 [2020-10-20 00:54:39,302 WARN L193 SmtUtils]: Spent 136.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 54 [2020-10-20 00:54:39,810 WARN L193 SmtUtils]: Spent 141.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 44 [2020-10-20 00:54:40,227 WARN L193 SmtUtils]: Spent 144.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 48 [2020-10-20 00:54:40,490 WARN L193 SmtUtils]: Spent 158.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 46 [2020-10-20 00:54:40,670 WARN L193 SmtUtils]: Spent 145.00 ms on a formula simplification. DAG size of input: 66 DAG size of output: 56 [2020-10-20 00:54:40,845 WARN L193 SmtUtils]: Spent 130.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 46 [2020-10-20 00:54:40,967 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-10-20 00:54:40,967 INFO L93 Difference]: Finished difference Result 631 states and 796 transitions. [2020-10-20 00:54:40,967 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2020-10-20 00:54:40,967 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 38 [2020-10-20 00:54:40,968 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-10-20 00:54:40,971 INFO L225 Difference]: With dead ends: 631 [2020-10-20 00:54:40,971 INFO L226 Difference]: Without dead ends: 569 [2020-10-20 00:54:40,972 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 652 ImplicationChecksByTransitivity, 7.1s TimeCoverageRelationStatistics Valid=427, Invalid=2435, Unknown=0, NotChecked=0, Total=2862 [2020-10-20 00:54:40,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 569 states. [2020-10-20 00:54:41,021 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 569 to 411. [2020-10-20 00:54:41,021 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 411 states. [2020-10-20 00:54:41,022 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 411 states to 411 states and 543 transitions. [2020-10-20 00:54:41,022 INFO L78 Accepts]: Start accepts. Automaton has 411 states and 543 transitions. Word has length 38 [2020-10-20 00:54:41,022 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-10-20 00:54:41,023 INFO L481 AbstractCegarLoop]: Abstraction has 411 states and 543 transitions. [2020-10-20 00:54:41,023 INFO L482 AbstractCegarLoop]: Interpolant automaton has 23 states. [2020-10-20 00:54:41,023 INFO L276 IsEmpty]: Start isEmpty. Operand 411 states and 543 transitions. [2020-10-20 00:54:41,024 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2020-10-20 00:54:41,024 INFO L414 BasicCegarLoop]: Found error trace [2020-10-20 00:54:41,024 INFO L422 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-10-20 00:54:41,224 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2020-10-20 00:54:41,225 INFO L429 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-10-20 00:54:41,225 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-10-20 00:54:41,226 INFO L82 PathProgramCache]: Analyzing trace with hash 729181046, now seen corresponding path program 1 times [2020-10-20 00:54:41,226 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-10-20 00:54:41,226 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [7514216] [2020-10-20 00:54:41,226 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-10-20 00:54:41,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2020-10-20 00:54:41,267 INFO L221 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2020-10-20 00:54:41,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2020-10-20 00:54:41,297 INFO L221 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2020-10-20 00:54:41,328 INFO L173 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2020-10-20 00:54:41,328 INFO L523 BasicCegarLoop]: Counterexample might be feasible [2020-10-20 00:54:41,328 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18 [2020-10-20 00:54:41,396 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.10 12:54:41 BoogieIcfgContainer [2020-10-20 00:54:41,396 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2020-10-20 00:54:41,397 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2020-10-20 00:54:41,397 INFO L271 PluginConnector]: Initializing Witness Printer... [2020-10-20 00:54:41,397 INFO L275 PluginConnector]: Witness Printer initialized [2020-10-20 00:54:41,398 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.10 12:53:37" (3/4) ... [2020-10-20 00:54:41,401 INFO L131 WitnessPrinter]: Generating witness for reachability counterexample [2020-10-20 00:54:41,489 INFO L141 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2020-10-20 00:54:41,489 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2020-10-20 00:54:41,492 INFO L168 Benchmark]: Toolchain (without parser) took 64882.16 ms. Allocated memory was 39.8 MB in the beginning and 155.2 MB in the end (delta: 115.3 MB). Free memory was 17.2 MB in the beginning and 106.6 MB in the end (delta: -89.4 MB). Peak memory consumption was 26.0 MB. Max. memory is 14.3 GB. [2020-10-20 00:54:41,493 INFO L168 Benchmark]: CDTParser took 0.27 ms. Allocated memory is still 30.9 MB. Free memory was 17.2 MB in the beginning and 17.2 MB in the end (delta: 32.9 kB). Peak memory consumption was 32.9 kB. Max. memory is 14.3 GB. [2020-10-20 00:54:41,493 INFO L168 Benchmark]: CACSL2BoogieTranslator took 342.83 ms. Allocated memory was 39.8 MB in the beginning and 40.9 MB in the end (delta: 1.0 MB). Free memory was 16.3 MB in the beginning and 14.7 MB in the end (delta: 1.6 MB). Peak memory consumption was 6.7 MB. Max. memory is 14.3 GB. [2020-10-20 00:54:41,493 INFO L168 Benchmark]: Boogie Procedure Inliner took 48.88 ms. Allocated memory is still 40.9 MB. Free memory was 14.6 MB in the beginning and 12.2 MB in the end (delta: 2.4 MB). Peak memory consumption was 2.4 MB. Max. memory is 14.3 GB. [2020-10-20 00:54:41,495 INFO L168 Benchmark]: Boogie Preprocessor took 43.85 ms. Allocated memory was 40.9 MB in the beginning and 42.5 MB in the end (delta: 1.6 MB). Free memory was 12.2 MB in the beginning and 25.3 MB in the end (delta: -13.1 MB). Peak memory consumption was 1.5 MB. Max. memory is 14.3 GB. [2020-10-20 00:54:41,496 INFO L168 Benchmark]: RCFGBuilder took 556.62 ms. Allocated memory is still 42.5 MB. Free memory was 25.3 MB in the beginning and 17.0 MB in the end (delta: 8.3 MB). Peak memory consumption was 15.1 MB. Max. memory is 14.3 GB. [2020-10-20 00:54:41,496 INFO L168 Benchmark]: TraceAbstraction took 63783.54 ms. Allocated memory was 42.5 MB in the beginning and 155.2 MB in the end (delta: 112.7 MB). Free memory was 16.5 MB in the beginning and 113.7 MB in the end (delta: -97.3 MB). Peak memory consumption was 15.5 MB. Max. memory is 14.3 GB. [2020-10-20 00:54:41,497 INFO L168 Benchmark]: Witness Printer took 92.91 ms. Allocated memory is still 155.2 MB. Free memory was 113.7 MB in the beginning and 106.6 MB in the end (delta: 7.2 MB). Peak memory consumption was 7.2 MB. Max. memory is 14.3 GB. [2020-10-20 00:54:41,504 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.27 ms. Allocated memory is still 30.9 MB. Free memory was 17.2 MB in the beginning and 17.2 MB in the end (delta: 32.9 kB). Peak memory consumption was 32.9 kB. Max. memory is 14.3 GB. * CACSL2BoogieTranslator took 342.83 ms. Allocated memory was 39.8 MB in the beginning and 40.9 MB in the end (delta: 1.0 MB). Free memory was 16.3 MB in the beginning and 14.7 MB in the end (delta: 1.6 MB). Peak memory consumption was 6.7 MB. Max. memory is 14.3 GB. * Boogie Procedure Inliner took 48.88 ms. Allocated memory is still 40.9 MB. Free memory was 14.6 MB in the beginning and 12.2 MB in the end (delta: 2.4 MB). Peak memory consumption was 2.4 MB. Max. memory is 14.3 GB. * Boogie Preprocessor took 43.85 ms. Allocated memory was 40.9 MB in the beginning and 42.5 MB in the end (delta: 1.6 MB). Free memory was 12.2 MB in the beginning and 25.3 MB in the end (delta: -13.1 MB). Peak memory consumption was 1.5 MB. Max. memory is 14.3 GB. * RCFGBuilder took 556.62 ms. Allocated memory is still 42.5 MB. Free memory was 25.3 MB in the beginning and 17.0 MB in the end (delta: 8.3 MB). Peak memory consumption was 15.1 MB. Max. memory is 14.3 GB. * TraceAbstraction took 63783.54 ms. Allocated memory was 42.5 MB in the beginning and 155.2 MB in the end (delta: 112.7 MB). Free memory was 16.5 MB in the beginning and 113.7 MB in the end (delta: -97.3 MB). Peak memory consumption was 15.5 MB. Max. memory is 14.3 GB. * Witness Printer took 92.91 ms. Allocated memory is still 155.2 MB. Free memory was 113.7 MB in the beginning and 106.6 MB in the end (delta: 7.2 MB). Peak memory consumption was 7.2 MB. Max. memory is 14.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - CounterExampleResult [Line: 7]: a call of __VERIFIER_error() is reachable a call of __VERIFIER_error() is reachable We found a FailurePath: [L16] int INFINITY = 899; VAL [INFINITY=899] [L18] int nodecount = __VERIFIER_nondet_int(); [L19] int edgecount = __VERIFIER_nondet_int(); [L20] COND FALSE !(!(0 <= nodecount && nodecount <= 4)) VAL [INFINITY=899] [L21] COND FALSE !(!(0 <= edgecount && edgecount <= 19)) [L22] int source = 0; [L23] int Source[20] = {0,4,1,1,0,0,1,3,4,4,2,2,3,0,0,3,1,2,2,3}; [L24] int Dest[20] = {1,3,4,1,1,4,3,4,3,0,0,0,0,2,3,0,2,1,0,4}; [L25] int Weight[20] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}; [L26] int distance[5]; [L27] int x,y; [L28] int i,j; [L30] i = 0 VAL [INFINITY=899] [L30] COND TRUE i < nodecount VAL [INFINITY=899] [L31] COND TRUE i == source [L32] distance[i] = 0 VAL [INFINITY=899] [L30] i++ VAL [INFINITY=899] [L30] COND TRUE i < nodecount VAL [INFINITY=899] [L31] COND FALSE !(i == source) [L35] distance[i] = INFINITY VAL [INFINITY=899] [L30] i++ VAL [INFINITY=899] [L30] COND FALSE !(i < nodecount) VAL [INFINITY=899] [L39] i = 0 VAL [INFINITY=899] [L39] COND TRUE i < nodecount [L41] j = 0 VAL [INFINITY=899] [L41] COND TRUE j < edgecount [L43] EXPR Dest[j] [L43] x = Dest[j] [L44] EXPR Source[j] [L44] y = Source[j] [L45] EXPR distance[x] [L45] EXPR distance[y] [L45] EXPR Weight[j] VAL [INFINITY=899] [L45] COND TRUE distance[x] > distance[y] + Weight[j] [L47] distance[x] = -1 VAL [INFINITY=899] [L41] j++ VAL [INFINITY=899] [L41] COND FALSE !(j < edgecount) VAL [INFINITY=899] [L39] i++ VAL [INFINITY=899] [L39] COND TRUE i < nodecount [L41] j = 0 VAL [INFINITY=899] [L41] COND TRUE j < edgecount [L43] EXPR Dest[j] [L43] x = Dest[j] [L44] EXPR Source[j] [L44] y = Source[j] [L45] EXPR distance[x] [L45] EXPR distance[y] [L45] EXPR Weight[j] VAL [INFINITY=899] [L45] COND FALSE !(distance[x] > distance[y] + Weight[j]) [L41] j++ VAL [INFINITY=899] [L41] COND FALSE !(j < edgecount) VAL [INFINITY=899] [L39] i++ VAL [INFINITY=899] [L39] COND FALSE !(i < nodecount) VAL [INFINITY=899] [L51] i = 0 VAL [INFINITY=899] [L51] COND TRUE i < edgecount [L53] EXPR Dest[i] [L53] x = Dest[i] [L54] EXPR Source[i] [L54] y = Source[i] [L55] EXPR distance[x] [L55] EXPR distance[y] [L55] EXPR Weight[i] VAL [INFINITY=899] [L55] COND FALSE !(distance[x] > distance[y] + Weight[i]) [L51] i++ VAL [INFINITY=899] [L51] COND FALSE !(i < edgecount) VAL [INFINITY=899] [L61] i = 0 VAL [INFINITY=899] [L61] COND TRUE i < nodecount [L63] distance[i] [L11] COND FALSE !(!(cond)) VAL [INFINITY=899] [L61] i++ VAL [INFINITY=899] [L61] COND TRUE i < nodecount [L63] distance[i] [L11] COND TRUE !(cond) VAL [INFINITY=899] [L7] __assert_fail("0", "eureka_01-1.c", 7, "reach_error") VAL [INFINITY=899] - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 29 locations, 1 error locations. Started 1 CEGAR loops. VerificationResult: UNSAFE, OverallTime: 63.6s, OverallIterations: 19, TraceHistogramMax: 3, AutomataDifference: 40.9s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 596 SDtfs, 2984 SDslu, 2992 SDs, 0 SdLazy, 4391 SolverSat, 1562 SolverUnsat, 1 SolverUnknown, 0 SolverNotchecked, 8.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 760 GetRequests, 355 SyntacticMatches, 3 SemanticMatches, 402 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3414 ImplicationChecksByTransitivity, 39.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=411occurred in iteration=18, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.4s AutomataMinimizationTime, 18 MinimizatonAttempts, 1214 StatesRemovedByMinimization, 18 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.2s SsaConstructionTime, 1.8s SatisfiabilityAnalysisTime, 16.2s InterpolantComputationTime, 959 NumberOfCodeBlocks, 956 NumberOfCodeBlocksAsserted, 46 NumberOfCheckSat, 888 ConstructedInterpolants, 82 QuantifiedInterpolants, 516510 SizeOfPredicates, 140 NumberOfNonLiveVariables, 3731 ConjunctsInSsa, 278 ConjunctsInUnsatCore, 33 InterpolantComputations, 4 PerfectInterpolantSequences, 161/363 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! Received shutdown request...