java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/lustre/Gas.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 18:35:21,298 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 18:35:21,300 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 18:35:21,311 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 18:35:21,312 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 18:35:21,313 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 18:35:21,314 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 18:35:21,318 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 18:35:21,319 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 18:35:21,321 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 18:35:21,322 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 18:35:21,322 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 18:35:21,323 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 18:35:21,327 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 18:35:21,328 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 18:35:21,329 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 18:35:21,330 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 18:35:21,343 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 18:35:21,344 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 18:35:21,345 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 18:35:21,346 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 18:35:21,348 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 18:35:21,348 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 18:35:21,349 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 18:35:21,349 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 18:35:21,350 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 18:35:21,351 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 18:35:21,351 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 18:35:21,352 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 18:35:21,353 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 18:35:21,353 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 18:35:21,354 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 18:35:21,354 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 18:35:21,355 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 18:35:21,355 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 18:35:21,355 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 18:35:21,368 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 18:35:21,368 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 18:35:21,368 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 18:35:21,369 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 18:35:21,370 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 18:35:21,370 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 18:35:21,370 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 18:35:21,370 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 18:35:21,370 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 18:35:21,371 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 18:35:21,371 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 18:35:21,371 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 18:35:21,371 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 18:35:21,371 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 18:35:21,371 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 18:35:21,372 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 18:35:21,372 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 18:35:21,372 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 18:35:21,372 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 18:35:21,373 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 18:35:21,374 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 18:35:21,413 INFO ]: Repository-Root is: /tmp [2018-06-22 18:35:21,427 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 18:35:21,431 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 18:35:21,432 INFO ]: Initializing SmtParser... [2018-06-22 18:35:21,432 INFO ]: SmtParser initialized [2018-06-22 18:35:21,433 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/Gas.smt2 [2018-06-22 18:35:21,434 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 18:35:21,526 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/Gas.smt2 unknown [2018-06-22 18:35:21,834 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/Gas.smt2 [2018-06-22 18:35:21,838 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 18:35:21,848 INFO ]: Walking toolchain with 4 elements. [2018-06-22 18:35:21,849 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 18:35:21,849 INFO ]: Initializing ChcToBoogie... [2018-06-22 18:35:21,849 INFO ]: ChcToBoogie initialized [2018-06-22 18:35:21,852 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 06:35:21" (1/1) ... [2018-06-22 18:35:21,899 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:35:21 Unit [2018-06-22 18:35:21,900 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 18:35:21,900 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 18:35:21,900 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 18:35:21,900 INFO ]: Boogie Preprocessor initialized [2018-06-22 18:35:21,924 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:35:21" (1/1) ... [2018-06-22 18:35:21,924 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:35:21" (1/1) ... [2018-06-22 18:35:21,933 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:35:21" (1/1) ... [2018-06-22 18:35:21,933 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:35:21" (1/1) ... [2018-06-22 18:35:21,944 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:35:21" (1/1) ... [2018-06-22 18:35:21,945 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:35:21" (1/1) ... [2018-06-22 18:35:21,946 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:35:21" (1/1) ... [2018-06-22 18:35:21,953 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 18:35:21,954 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 18:35:21,954 INFO ]: Initializing RCFGBuilder... [2018-06-22 18:35:21,954 INFO ]: RCFGBuilder initialized [2018-06-22 18:35:21,955 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:35:21" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 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 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 18:35:21,971 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 18:35:21,971 INFO ]: Found specification of procedure False [2018-06-22 18:35:21,971 INFO ]: Found implementation of procedure False [2018-06-22 18:35:21,971 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 18:35:21,971 INFO ]: Found specification of procedure state [2018-06-22 18:35:21,971 INFO ]: Found implementation of procedure state [2018-06-22 18:35:21,971 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 18:35:21,971 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 18:35:21,971 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 18:35:22,223 INFO ]: Using library mode [2018-06-22 18:35:22,223 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 06:35:22 BoogieIcfgContainer [2018-06-22 18:35:22,224 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 18:35:22,225 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 18:35:22,225 INFO ]: Initializing TraceAbstraction... [2018-06-22 18:35:22,228 INFO ]: TraceAbstraction initialized [2018-06-22 18:35:22,228 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 06:35:21" (1/3) ... [2018-06-22 18:35:22,229 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@120161c4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 06:35:22, skipping insertion in model container [2018-06-22 18:35:22,229 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:35:21" (2/3) ... [2018-06-22 18:35:22,229 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@120161c4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 06:35:22, skipping insertion in model container [2018-06-22 18:35:22,229 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 06:35:22" (3/3) ... [2018-06-22 18:35:22,231 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 18:35:22,240 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 18:35:22,248 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 18:35:22,287 INFO ]: Using default assertion order modulation [2018-06-22 18:35:22,287 INFO ]: Interprodecural is true [2018-06-22 18:35:22,287 INFO ]: Hoare is false [2018-06-22 18:35:22,287 INFO ]: Compute interpolants for FPandBP [2018-06-22 18:35:22,287 INFO ]: Backedges is TWOTRACK [2018-06-22 18:35:22,287 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 18:35:22,288 INFO ]: Difference is false [2018-06-22 18:35:22,288 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 18:35:22,288 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 18:35:22,301 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 18:35:22,311 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 18:35:22,311 INFO ]: Found error trace [2018-06-22 18:35:22,311 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:22,313 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:22,318 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 18:35:22,320 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:22,321 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:22,353 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:22,353 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:35:22,353 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:22,405 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:22,525 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 18:35:22,527 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 18:35:22,527 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 18:35:22,528 INFO ]: Interpolant automaton has 4 states [2018-06-22 18:35:22,538 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 18:35:22,539 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 18:35:22,540 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 18:35:22,639 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:22,639 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 18:35:22,640 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 18:35:22,641 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 18:35:22,641 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:22,650 INFO ]: With dead ends: 13 [2018-06-22 18:35:22,650 INFO ]: Without dead ends: 13 [2018-06-22 18:35:22,652 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 18:35:22,665 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 18:35:22,697 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 18:35:22,698 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 18:35:22,699 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 18:35:22,700 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 18:35:22,700 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:22,700 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 18:35:22,700 INFO ]: Interpolant automaton has 4 states. [2018-06-22 18:35:22,700 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 18:35:22,701 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 18:35:22,701 INFO ]: Found error trace [2018-06-22 18:35:22,701 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:22,702 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:22,702 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 18:35:22,702 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:22,702 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:22,703 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:22,703 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:35:22,703 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:22,757 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:23,157 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 18:35:23,157 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:23,157 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:23,166 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:35:23,220 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:23,227 INFO ]: Computing forward predicates... [2018-06-22 18:35:23,616 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 7 DAG size of output: 5 [2018-06-22 18:35:23,686 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 18:35:23,708 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:23,708 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 18:35:23,708 INFO ]: Interpolant automaton has 9 states [2018-06-22 18:35:23,708 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 18:35:23,709 INFO ]: CoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2018-06-22 18:35:23,709 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 18:35:24,084 WARN ]: Spent 121.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 15 [2018-06-22 18:35:24,206 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:24,206 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 18:35:24,206 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 18:35:24,206 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 18:35:24,206 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:24,207 INFO ]: With dead ends: 15 [2018-06-22 18:35:24,207 INFO ]: Without dead ends: 15 [2018-06-22 18:35:24,208 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2018-06-22 18:35:24,208 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 18:35:24,211 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 18:35:24,211 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 18:35:24,212 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 18:35:24,212 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 18:35:24,212 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:24,212 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 18:35:24,212 INFO ]: Interpolant automaton has 9 states. [2018-06-22 18:35:24,212 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 18:35:24,212 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 18:35:24,213 INFO ]: Found error trace [2018-06-22 18:35:24,213 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:24,213 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:24,213 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 18:35:24,213 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:24,213 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:24,214 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:24,214 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:35:24,214 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:24,252 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:24,546 WARN ]: Spent 152.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 [2018-06-22 18:35:24,873 WARN ]: Spent 238.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 20 [2018-06-22 18:35:24,923 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 18:35:24,923 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:24,923 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 18:35:24,937 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:25,000 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 18:35:25,000 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:25,003 INFO ]: Computing forward predicates... [2018-06-22 18:35:25,307 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 18:35:25,326 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:25,326 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 12 [2018-06-22 18:35:25,326 INFO ]: Interpolant automaton has 12 states [2018-06-22 18:35:25,326 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 18:35:25,326 INFO ]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2018-06-22 18:35:25,327 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 12 states. [2018-06-22 18:35:25,666 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:25,666 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 18:35:25,666 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 18:35:25,666 INFO ]: Start accepts. Automaton has 12 states. Word has length 17 [2018-06-22 18:35:25,667 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:25,667 INFO ]: With dead ends: 17 [2018-06-22 18:35:25,667 INFO ]: Without dead ends: 17 [2018-06-22 18:35:25,668 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=64, Invalid=176, Unknown=0, NotChecked=0, Total=240 [2018-06-22 18:35:25,668 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 18:35:25,670 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 18:35:25,670 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 18:35:25,671 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 18:35:25,671 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 18:35:25,671 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:25,671 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 18:35:25,671 INFO ]: Interpolant automaton has 12 states. [2018-06-22 18:35:25,671 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 18:35:25,672 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 18:35:25,672 INFO ]: Found error trace [2018-06-22 18:35:25,672 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:25,672 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:25,672 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 18:35:25,672 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:25,672 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:25,673 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:25,673 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:35:25,673 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:25,709 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:26,035 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 18:35:26,035 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:26,081 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:26,087 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 18:35:26,179 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 18:35:26,179 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:26,183 INFO ]: Computing forward predicates... [2018-06-22 18:35:26,692 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 18:35:26,726 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:26,726 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2018-06-22 18:35:26,727 INFO ]: Interpolant automaton has 16 states [2018-06-22 18:35:26,727 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 18:35:26,727 INFO ]: CoverageRelationStatistics Valid=43, Invalid=197, Unknown=0, NotChecked=0, Total=240 [2018-06-22 18:35:26,727 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 16 states. [2018-06-22 18:35:27,010 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:27,011 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 18:35:27,011 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 18:35:27,011 INFO ]: Start accepts. Automaton has 16 states. Word has length 21 [2018-06-22 18:35:27,011 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:27,012 INFO ]: With dead ends: 19 [2018-06-22 18:35:27,012 INFO ]: Without dead ends: 19 [2018-06-22 18:35:27,012 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=101, Invalid=319, Unknown=0, NotChecked=0, Total=420 [2018-06-22 18:35:27,012 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 18:35:27,015 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 18:35:27,015 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 18:35:27,016 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 18:35:27,016 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 18:35:27,016 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:27,016 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 18:35:27,016 INFO ]: Interpolant automaton has 16 states. [2018-06-22 18:35:27,016 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 18:35:27,017 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 18:35:27,017 INFO ]: Found error trace [2018-06-22 18:35:27,017 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:27,017 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:27,017 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 18:35:27,017 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:27,017 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:27,017 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:27,017 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:35:27,018 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:27,070 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:27,382 INFO ]: Checked inductivity of 36 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-06-22 18:35:27,383 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:27,383 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:27,396 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 18:35:27,465 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 18:35:27,465 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:27,468 INFO ]: Computing forward predicates... [2018-06-22 18:35:27,961 INFO ]: Checked inductivity of 36 backedges. 0 proven. 23 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-06-22 18:35:27,981 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:27,981 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 17 [2018-06-22 18:35:27,981 INFO ]: Interpolant automaton has 17 states [2018-06-22 18:35:27,981 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 18:35:27,982 INFO ]: CoverageRelationStatistics Valid=56, Invalid=216, Unknown=0, NotChecked=0, Total=272 [2018-06-22 18:35:27,982 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 17 states. [2018-06-22 18:35:28,382 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:28,382 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 18:35:28,385 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 18:35:28,385 INFO ]: Start accepts. Automaton has 17 states. Word has length 25 [2018-06-22 18:35:28,385 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:28,386 INFO ]: With dead ends: 21 [2018-06-22 18:35:28,386 INFO ]: Without dead ends: 21 [2018-06-22 18:35:28,386 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=128, Invalid=378, Unknown=0, NotChecked=0, Total=506 [2018-06-22 18:35:28,386 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 18:35:28,391 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 18:35:28,391 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 18:35:28,392 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 18:35:28,392 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 18:35:28,392 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:28,392 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 18:35:28,392 INFO ]: Interpolant automaton has 17 states. [2018-06-22 18:35:28,392 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 18:35:28,393 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 18:35:28,393 INFO ]: Found error trace [2018-06-22 18:35:28,393 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:28,393 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:28,393 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 18:35:28,393 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:28,393 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:28,395 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:28,395 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:35:28,395 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:28,443 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:28,995 WARN ]: Spent 394.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 [2018-06-22 18:35:29,290 WARN ]: Spent 222.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-22 18:35:29,429 INFO ]: Checked inductivity of 55 backedges. 0 proven. 37 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-06-22 18:35:29,429 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:29,429 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:29,434 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 18:35:29,534 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 18:35:29,534 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:29,539 INFO ]: Computing forward predicates... [2018-06-22 18:35:29,840 INFO ]: Checked inductivity of 55 backedges. 0 proven. 39 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2018-06-22 18:35:29,859 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:29,859 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 21 [2018-06-22 18:35:29,859 INFO ]: Interpolant automaton has 21 states [2018-06-22 18:35:29,859 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 18:35:29,860 INFO ]: CoverageRelationStatistics Valid=61, Invalid=359, Unknown=0, NotChecked=0, Total=420 [2018-06-22 18:35:29,860 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 21 states. [2018-06-22 18:35:30,505 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:30,505 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 18:35:30,505 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 18:35:30,505 INFO ]: Start accepts. Automaton has 21 states. Word has length 29 [2018-06-22 18:35:30,506 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:30,506 INFO ]: With dead ends: 23 [2018-06-22 18:35:30,506 INFO ]: Without dead ends: 23 [2018-06-22 18:35:30,507 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 76 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=169, Invalid=587, Unknown=0, NotChecked=0, Total=756 [2018-06-22 18:35:30,507 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 18:35:30,510 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 18:35:30,510 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 18:35:30,510 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 18:35:30,510 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 18:35:30,511 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:30,511 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 18:35:30,511 INFO ]: Interpolant automaton has 21 states. [2018-06-22 18:35:30,511 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 18:35:30,512 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 18:35:30,512 INFO ]: Found error trace [2018-06-22 18:35:30,512 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:30,512 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:30,512 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-22 18:35:30,512 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:30,512 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:30,513 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:30,513 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:35:30,513 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:30,547 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:30,866 WARN ]: Spent 138.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 [2018-06-22 18:35:31,014 INFO ]: Checked inductivity of 78 backedges. 3 proven. 51 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-06-22 18:35:31,014 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:31,014 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:31,037 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 18:35:31,125 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 18:35:31,125 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:31,130 INFO ]: Computing forward predicates... [2018-06-22 18:35:31,363 INFO ]: Checked inductivity of 78 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2018-06-22 18:35:31,394 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:31,394 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 15] total 25 [2018-06-22 18:35:31,395 INFO ]: Interpolant automaton has 25 states [2018-06-22 18:35:31,395 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-22 18:35:31,395 INFO ]: CoverageRelationStatistics Valid=86, Invalid=514, Unknown=0, NotChecked=0, Total=600 [2018-06-22 18:35:31,396 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 25 states. [2018-06-22 18:35:31,849 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:31,849 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 18:35:31,850 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 18:35:31,850 INFO ]: Start accepts. Automaton has 25 states. Word has length 33 [2018-06-22 18:35:31,850 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:31,850 INFO ]: With dead ends: 25 [2018-06-22 18:35:31,851 INFO ]: Without dead ends: 25 [2018-06-22 18:35:31,851 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 132 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=236, Invalid=820, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 18:35:31,851 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 18:35:31,854 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 18:35:31,854 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 18:35:31,855 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 18:35:31,855 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 18:35:31,855 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:31,855 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 18:35:31,855 INFO ]: Interpolant automaton has 25 states. [2018-06-22 18:35:31,855 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 18:35:31,856 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 18:35:31,856 INFO ]: Found error trace [2018-06-22 18:35:31,856 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:31,856 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:31,856 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-22 18:35:31,856 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:31,856 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:31,857 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:31,857 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:35:31,857 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:31,890 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:32,453 WARN ]: Spent 377.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 [2018-06-22 18:35:32,753 WARN ]: Spent 225.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-22 18:35:33,054 WARN ]: Spent 200.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-22 18:35:33,390 INFO ]: Checked inductivity of 105 backedges. 6 proven. 67 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2018-06-22 18:35:33,390 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:33,390 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:33,397 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:35:33,476 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:33,481 INFO ]: Computing forward predicates... [2018-06-22 18:35:33,743 INFO ]: Checked inductivity of 105 backedges. 0 proven. 62 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2018-06-22 18:35:33,764 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:33,764 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 24 [2018-06-22 18:35:33,765 INFO ]: Interpolant automaton has 24 states [2018-06-22 18:35:33,765 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 18:35:33,765 INFO ]: CoverageRelationStatistics Valid=117, Invalid=435, Unknown=0, NotChecked=0, Total=552 [2018-06-22 18:35:33,765 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 24 states. [2018-06-22 18:35:34,162 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:34,162 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 18:35:34,162 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 18:35:34,162 INFO ]: Start accepts. Automaton has 24 states. Word has length 37 [2018-06-22 18:35:34,163 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:34,163 INFO ]: With dead ends: 27 [2018-06-22 18:35:34,163 INFO ]: Without dead ends: 27 [2018-06-22 18:35:34,164 INFO ]: 0 DeclaredPredicates, 63 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=272, Invalid=784, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 18:35:34,164 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 18:35:34,167 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 18:35:34,167 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 18:35:34,168 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 18:35:34,168 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 18:35:34,168 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:34,168 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 18:35:34,168 INFO ]: Interpolant automaton has 24 states. [2018-06-22 18:35:34,168 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 18:35:34,171 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 18:35:34,171 INFO ]: Found error trace [2018-06-22 18:35:34,171 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:34,171 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:34,171 INFO ]: Analyzing trace with hash 1618126293, now seen corresponding path program 8 times [2018-06-22 18:35:34,171 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:34,171 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:34,172 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:34,172 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:35:34,172 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:34,215 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:34,582 WARN ]: Spent 120.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 [2018-06-22 18:35:34,807 INFO ]: Checked inductivity of 136 backedges. 3 proven. 87 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2018-06-22 18:35:34,807 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:34,807 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:34,813 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 18:35:34,914 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 18:35:34,914 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:34,919 INFO ]: Computing forward predicates... [2018-06-22 18:35:35,199 INFO ]: Checked inductivity of 136 backedges. 0 proven. 79 refuted. 0 times theorem prover too weak. 57 trivial. 0 not checked. [2018-06-22 18:35:35,219 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:35,219 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14] total 26 [2018-06-22 18:35:35,219 INFO ]: Interpolant automaton has 26 states [2018-06-22 18:35:35,222 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-22 18:35:35,222 INFO ]: CoverageRelationStatistics Valid=142, Invalid=508, Unknown=0, NotChecked=0, Total=650 [2018-06-22 18:35:35,222 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 26 states. [2018-06-22 18:35:35,934 WARN ]: Spent 110.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 17 [2018-06-22 18:35:35,969 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:35,969 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 18:35:35,970 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 18:35:35,970 INFO ]: Start accepts. Automaton has 26 states. Word has length 41 [2018-06-22 18:35:35,970 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:35,970 INFO ]: With dead ends: 29 [2018-06-22 18:35:35,970 INFO ]: Without dead ends: 29 [2018-06-22 18:35:35,971 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 36 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 133 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=329, Invalid=931, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 18:35:35,971 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 18:35:35,976 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 18:35:35,976 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 18:35:35,977 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 18:35:35,977 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 18:35:35,977 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:35,977 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 18:35:35,977 INFO ]: Interpolant automaton has 26 states. [2018-06-22 18:35:35,977 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 18:35:35,979 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 18:35:35,979 INFO ]: Found error trace [2018-06-22 18:35:35,979 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:35,979 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:35,979 INFO ]: Analyzing trace with hash 996918775, now seen corresponding path program 9 times [2018-06-22 18:35:35,979 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:35,979 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:35,979 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:35,979 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:35:35,979 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:36,017 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:36,556 INFO ]: Checked inductivity of 171 backedges. 8 proven. 107 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2018-06-22 18:35:36,556 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:36,636 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:36,645 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 18:35:36,833 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 18:35:36,833 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:36,839 INFO ]: Computing forward predicates... [2018-06-22 18:35:37,396 INFO ]: Checked inductivity of 171 backedges. 0 proven. 117 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2018-06-22 18:35:37,417 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:37,417 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 30 [2018-06-22 18:35:37,417 INFO ]: Interpolant automaton has 30 states [2018-06-22 18:35:37,418 INFO ]: Constructing interpolant automaton starting with 30 interpolants. [2018-06-22 18:35:37,418 INFO ]: CoverageRelationStatistics Valid=147, Invalid=723, Unknown=0, NotChecked=0, Total=870 [2018-06-22 18:35:37,418 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 30 states. [2018-06-22 18:35:38,230 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:38,230 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 18:35:38,230 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 18:35:38,231 INFO ]: Start accepts. Automaton has 30 states. Word has length 45 [2018-06-22 18:35:38,231 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:38,231 INFO ]: With dead ends: 31 [2018-06-22 18:35:38,231 INFO ]: Without dead ends: 31 [2018-06-22 18:35:38,232 INFO ]: 0 DeclaredPredicates, 77 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 211 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=391, Invalid=1249, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 18:35:38,232 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 18:35:38,235 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 18:35:38,235 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 18:35:38,236 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 18:35:38,236 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 18:35:38,236 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:38,236 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 18:35:38,236 INFO ]: Interpolant automaton has 30 states. [2018-06-22 18:35:38,236 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 18:35:38,237 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 18:35:38,237 INFO ]: Found error trace [2018-06-22 18:35:38,237 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:38,237 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:38,237 INFO ]: Analyzing trace with hash -570306151, now seen corresponding path program 10 times [2018-06-22 18:35:38,237 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:38,237 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:38,238 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:38,238 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:35:38,238 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:38,275 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:38,783 WARN ]: Spent 320.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 [2018-06-22 18:35:39,016 INFO ]: Checked inductivity of 210 backedges. 12 proven. 131 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2018-06-22 18:35:39,016 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:39,016 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:39,023 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 18:35:39,134 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 18:35:39,134 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:39,140 INFO ]: Computing forward predicates... [2018-06-22 18:35:40,112 INFO ]: Checked inductivity of 210 backedges. 0 proven. 134 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2018-06-22 18:35:40,132 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:40,132 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 32 [2018-06-22 18:35:40,132 INFO ]: Interpolant automaton has 32 states [2018-06-22 18:35:40,132 INFO ]: Constructing interpolant automaton starting with 32 interpolants. [2018-06-22 18:35:40,133 INFO ]: CoverageRelationStatistics Valid=196, Invalid=796, Unknown=0, NotChecked=0, Total=992 [2018-06-22 18:35:40,133 INFO ]: Start difference. First operand 31 states and 32 transitions. Second operand 32 states. [2018-06-22 18:35:40,814 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:40,815 INFO ]: Finished difference Result 33 states and 34 transitions. [2018-06-22 18:35:40,815 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 18:35:40,815 INFO ]: Start accepts. Automaton has 32 states. Word has length 49 [2018-06-22 18:35:40,815 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:40,816 INFO ]: With dead ends: 33 [2018-06-22 18:35:40,816 INFO ]: Without dead ends: 33 [2018-06-22 18:35:40,816 INFO ]: 0 DeclaredPredicates, 84 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 226 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=480, Invalid=1412, Unknown=0, NotChecked=0, Total=1892 [2018-06-22 18:35:40,817 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-22 18:35:40,820 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 33. [2018-06-22 18:35:40,820 INFO ]: Start removeUnreachable. Operand 33 states. [2018-06-22 18:35:40,821 INFO ]: Finished removeUnreachable. Reduced from 33 states to 33 states and 34 transitions. [2018-06-22 18:35:40,821 INFO ]: Start accepts. Automaton has 33 states and 34 transitions. Word has length 49 [2018-06-22 18:35:40,821 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:40,821 INFO ]: Abstraction has 33 states and 34 transitions. [2018-06-22 18:35:40,821 INFO ]: Interpolant automaton has 32 states. [2018-06-22 18:35:40,821 INFO ]: Start isEmpty. Operand 33 states and 34 transitions. [2018-06-22 18:35:40,822 INFO ]: Finished isEmpty. Found accepting run of length 54 [2018-06-22 18:35:40,822 INFO ]: Found error trace [2018-06-22 18:35:40,822 INFO ]: trace histogram [12, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:40,822 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:40,822 INFO ]: Analyzing trace with hash 1955719355, now seen corresponding path program 11 times [2018-06-22 18:35:40,822 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:40,822 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:40,823 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:40,823 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:35:40,823 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:40,866 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:41,245 WARN ]: Spent 178.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 [2018-06-22 18:35:41,469 WARN ]: Spent 195.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 20 [2018-06-22 18:35:41,703 INFO ]: Checked inductivity of 253 backedges. 18 proven. 151 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-06-22 18:35:41,703 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:41,725 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:41,734 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 18:35:41,926 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2018-06-22 18:35:41,926 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:41,933 INFO ]: Computing forward predicates... [2018-06-22 18:35:42,365 INFO ]: Checked inductivity of 253 backedges. 0 proven. 174 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2018-06-22 18:35:42,386 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:42,386 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 20] total 34 [2018-06-22 18:35:42,387 INFO ]: Interpolant automaton has 34 states [2018-06-22 18:35:42,387 INFO ]: Constructing interpolant automaton starting with 34 interpolants. [2018-06-22 18:35:42,387 INFO ]: CoverageRelationStatistics Valid=140, Invalid=982, Unknown=0, NotChecked=0, Total=1122 [2018-06-22 18:35:42,387 INFO ]: Start difference. First operand 33 states and 34 transitions. Second operand 34 states. [2018-06-22 18:35:43,697 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:43,697 INFO ]: Finished difference Result 35 states and 36 transitions. [2018-06-22 18:35:43,697 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-22 18:35:43,697 INFO ]: Start accepts. Automaton has 34 states. Word has length 53 [2018-06-22 18:35:43,698 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:43,698 INFO ]: With dead ends: 35 [2018-06-22 18:35:43,698 INFO ]: Without dead ends: 35 [2018-06-22 18:35:43,699 INFO ]: 0 DeclaredPredicates, 91 GetRequests, 45 SyntacticMatches, 1 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 314 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=478, Invalid=1684, Unknown=0, NotChecked=0, Total=2162 [2018-06-22 18:35:43,699 INFO ]: Start minimizeSevpa. Operand 35 states. [2018-06-22 18:35:43,702 INFO ]: Finished minimizeSevpa. Reduced states from 35 to 35. [2018-06-22 18:35:43,703 INFO ]: Start removeUnreachable. Operand 35 states. [2018-06-22 18:35:43,703 INFO ]: Finished removeUnreachable. Reduced from 35 states to 35 states and 36 transitions. [2018-06-22 18:35:43,703 INFO ]: Start accepts. Automaton has 35 states and 36 transitions. Word has length 53 [2018-06-22 18:35:43,703 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:43,703 INFO ]: Abstraction has 35 states and 36 transitions. [2018-06-22 18:35:43,703 INFO ]: Interpolant automaton has 34 states. [2018-06-22 18:35:43,703 INFO ]: Start isEmpty. Operand 35 states and 36 transitions. [2018-06-22 18:35:43,705 INFO ]: Finished isEmpty. Found accepting run of length 58 [2018-06-22 18:35:43,705 INFO ]: Found error trace [2018-06-22 18:35:43,705 INFO ]: trace histogram [13, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:43,705 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:43,705 INFO ]: Analyzing trace with hash -2085541027, now seen corresponding path program 12 times [2018-06-22 18:35:43,705 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:43,705 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:43,705 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:43,705 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:35:43,705 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:43,744 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:44,337 INFO ]: Checked inductivity of 300 backedges. 14 proven. 184 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2018-06-22 18:35:44,337 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:44,337 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:44,342 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 18:35:44,540 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 13 check-sat command(s) [2018-06-22 18:35:44,540 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:44,552 INFO ]: Computing forward predicates... [2018-06-22 18:35:45,328 INFO ]: Checked inductivity of 300 backedges. 0 proven. 209 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2018-06-22 18:35:45,349 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:45,349 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 21] total 37 [2018-06-22 18:35:45,350 INFO ]: Interpolant automaton has 37 states [2018-06-22 18:35:45,350 INFO ]: Constructing interpolant automaton starting with 37 interpolants. [2018-06-22 18:35:45,350 INFO ]: CoverageRelationStatistics Valid=216, Invalid=1116, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 18:35:45,350 INFO ]: Start difference. First operand 35 states and 36 transitions. Second operand 37 states. [2018-06-22 18:35:46,218 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:46,218 INFO ]: Finished difference Result 37 states and 38 transitions. [2018-06-22 18:35:46,218 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-06-22 18:35:46,218 INFO ]: Start accepts. Automaton has 37 states. Word has length 57 [2018-06-22 18:35:46,219 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:46,219 INFO ]: With dead ends: 37 [2018-06-22 18:35:46,219 INFO ]: Without dead ends: 37 [2018-06-22 18:35:46,220 INFO ]: 0 DeclaredPredicates, 98 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 355 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=603, Invalid=1947, Unknown=0, NotChecked=0, Total=2550 [2018-06-22 18:35:46,220 INFO ]: Start minimizeSevpa. Operand 37 states. [2018-06-22 18:35:46,227 INFO ]: Finished minimizeSevpa. Reduced states from 37 to 37. [2018-06-22 18:35:46,227 INFO ]: Start removeUnreachable. Operand 37 states. [2018-06-22 18:35:46,227 INFO ]: Finished removeUnreachable. Reduced from 37 states to 37 states and 38 transitions. [2018-06-22 18:35:46,227 INFO ]: Start accepts. Automaton has 37 states and 38 transitions. Word has length 57 [2018-06-22 18:35:46,228 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:46,228 INFO ]: Abstraction has 37 states and 38 transitions. [2018-06-22 18:35:46,228 INFO ]: Interpolant automaton has 37 states. [2018-06-22 18:35:46,228 INFO ]: Start isEmpty. Operand 37 states and 38 transitions. [2018-06-22 18:35:46,228 INFO ]: Finished isEmpty. Found accepting run of length 62 [2018-06-22 18:35:46,228 INFO ]: Found error trace [2018-06-22 18:35:46,229 INFO ]: trace histogram [14, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:46,231 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:46,232 INFO ]: Analyzing trace with hash 976009599, now seen corresponding path program 13 times [2018-06-22 18:35:46,232 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:46,232 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:46,232 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:46,232 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:35:46,232 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:46,272 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:46,589 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 [2018-06-22 18:35:46,915 INFO ]: Checked inductivity of 351 backedges. 20 proven. 215 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2018-06-22 18:35:46,915 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:46,962 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:46,967 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:35:47,106 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:47,113 INFO ]: Computing forward predicates... [2018-06-22 18:35:47,825 INFO ]: Checked inductivity of 351 backedges. 0 proven. 194 refuted. 0 times theorem prover too weak. 157 trivial. 0 not checked. [2018-06-22 18:35:47,846 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:47,846 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 19] total 36 [2018-06-22 18:35:47,847 INFO ]: Interpolant automaton has 36 states [2018-06-22 18:35:47,847 INFO ]: Constructing interpolant automaton starting with 36 interpolants. [2018-06-22 18:35:47,847 INFO ]: CoverageRelationStatistics Valid=312, Invalid=948, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 18:35:47,847 INFO ]: Start difference. First operand 37 states and 38 transitions. Second operand 36 states. [2018-06-22 18:35:48,524 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:48,524 INFO ]: Finished difference Result 39 states and 40 transitions. [2018-06-22 18:35:48,527 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-06-22 18:35:48,527 INFO ]: Start accepts. Automaton has 36 states. Word has length 61 [2018-06-22 18:35:48,528 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:48,528 INFO ]: With dead ends: 39 [2018-06-22 18:35:48,528 INFO ]: Without dead ends: 39 [2018-06-22 18:35:48,529 INFO ]: 0 DeclaredPredicates, 105 GetRequests, 56 SyntacticMatches, 0 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 278 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=704, Invalid=1846, Unknown=0, NotChecked=0, Total=2550 [2018-06-22 18:35:48,529 INFO ]: Start minimizeSevpa. Operand 39 states. [2018-06-22 18:35:48,533 INFO ]: Finished minimizeSevpa. Reduced states from 39 to 39. [2018-06-22 18:35:48,533 INFO ]: Start removeUnreachable. Operand 39 states. [2018-06-22 18:35:48,534 INFO ]: Finished removeUnreachable. Reduced from 39 states to 39 states and 40 transitions. [2018-06-22 18:35:48,534 INFO ]: Start accepts. Automaton has 39 states and 40 transitions. Word has length 61 [2018-06-22 18:35:48,534 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:48,534 INFO ]: Abstraction has 39 states and 40 transitions. [2018-06-22 18:35:48,534 INFO ]: Interpolant automaton has 36 states. [2018-06-22 18:35:48,534 INFO ]: Start isEmpty. Operand 39 states and 40 transitions. [2018-06-22 18:35:48,536 INFO ]: Finished isEmpty. Found accepting run of length 66 [2018-06-22 18:35:48,536 INFO ]: Found error trace [2018-06-22 18:35:48,536 INFO ]: trace histogram [15, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:48,536 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:48,536 INFO ]: Analyzing trace with hash 1124709153, now seen corresponding path program 14 times [2018-06-22 18:35:48,536 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:48,536 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:48,537 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:48,537 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:35:48,537 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:48,579 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:49,035 WARN ]: Spent 224.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 [2018-06-22 18:35:49,670 WARN ]: Spent 244.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 6 [2018-06-22 18:35:49,731 INFO ]: Checked inductivity of 406 backedges. 12 proven. 250 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2018-06-22 18:35:49,731 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:49,731 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:49,737 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 18:35:49,881 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 18:35:49,881 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:49,887 INFO ]: Computing forward predicates... [2018-06-22 18:35:50,790 INFO ]: Checked inductivity of 406 backedges. 0 proven. 223 refuted. 0 times theorem prover too weak. 183 trivial. 0 not checked. [2018-06-22 18:35:50,810 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:50,811 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 20] total 38 [2018-06-22 18:35:50,811 INFO ]: Interpolant automaton has 38 states [2018-06-22 18:35:50,811 INFO ]: Constructing interpolant automaton starting with 38 interpolants. [2018-06-22 18:35:50,811 INFO ]: CoverageRelationStatistics Valid=355, Invalid=1051, Unknown=0, NotChecked=0, Total=1406 [2018-06-22 18:35:50,811 INFO ]: Start difference. First operand 39 states and 40 transitions. Second operand 38 states. [2018-06-22 18:35:51,561 WARN ]: Spent 374.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 19 [2018-06-22 18:35:51,924 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:51,924 INFO ]: Finished difference Result 41 states and 42 transitions. [2018-06-22 18:35:51,959 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-22 18:35:51,959 INFO ]: Start accepts. Automaton has 38 states. Word has length 65 [2018-06-22 18:35:51,960 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:51,960 INFO ]: With dead ends: 41 [2018-06-22 18:35:51,960 INFO ]: Without dead ends: 41 [2018-06-22 18:35:51,961 INFO ]: 0 DeclaredPredicates, 112 GetRequests, 60 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 313 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=797, Invalid=2065, Unknown=0, NotChecked=0, Total=2862 [2018-06-22 18:35:51,961 INFO ]: Start minimizeSevpa. Operand 41 states. [2018-06-22 18:35:51,965 INFO ]: Finished minimizeSevpa. Reduced states from 41 to 41. [2018-06-22 18:35:51,966 INFO ]: Start removeUnreachable. Operand 41 states. [2018-06-22 18:35:51,970 INFO ]: Finished removeUnreachable. Reduced from 41 states to 41 states and 42 transitions. [2018-06-22 18:35:51,970 INFO ]: Start accepts. Automaton has 41 states and 42 transitions. Word has length 65 [2018-06-22 18:35:51,971 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:51,971 INFO ]: Abstraction has 41 states and 42 transitions. [2018-06-22 18:35:51,971 INFO ]: Interpolant automaton has 38 states. [2018-06-22 18:35:51,971 INFO ]: Start isEmpty. Operand 41 states and 42 transitions. [2018-06-22 18:35:51,972 INFO ]: Finished isEmpty. Found accepting run of length 70 [2018-06-22 18:35:51,972 INFO ]: Found error trace [2018-06-22 18:35:51,972 INFO ]: trace histogram [16, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:51,972 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:51,972 INFO ]: Analyzing trace with hash 394606659, now seen corresponding path program 15 times [2018-06-22 18:35:51,972 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:51,972 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:51,972 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:51,972 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:35:51,972 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:52,017 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:52,658 INFO ]: Checked inductivity of 465 backedges. 21 proven. 282 refuted. 0 times theorem prover too weak. 162 trivial. 0 not checked. [2018-06-22 18:35:52,658 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:52,658 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:52,664 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 18:35:52,914 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2018-06-22 18:35:52,914 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:52,923 INFO ]: Computing forward predicates... [2018-06-22 18:35:53,467 INFO ]: Checked inductivity of 465 backedges. 0 proven. 309 refuted. 0 times theorem prover too weak. 156 trivial. 0 not checked. [2018-06-22 18:35:53,488 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:53,488 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23] total 42 [2018-06-22 18:35:53,488 INFO ]: Interpolant automaton has 42 states [2018-06-22 18:35:53,489 INFO ]: Constructing interpolant automaton starting with 42 interpolants. [2018-06-22 18:35:53,489 INFO ]: CoverageRelationStatistics Valid=324, Invalid=1398, Unknown=0, NotChecked=0, Total=1722 [2018-06-22 18:35:53,489 INFO ]: Start difference. First operand 41 states and 42 transitions. Second operand 42 states. [2018-06-22 18:35:54,399 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:54,399 INFO ]: Finished difference Result 43 states and 44 transitions. [2018-06-22 18:35:54,400 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-06-22 18:35:54,400 INFO ]: Start accepts. Automaton has 42 states. Word has length 69 [2018-06-22 18:35:54,400 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:54,400 INFO ]: With dead ends: 43 [2018-06-22 18:35:54,400 INFO ]: Without dead ends: 43 [2018-06-22 18:35:54,401 INFO ]: 0 DeclaredPredicates, 119 GetRequests, 62 SyntacticMatches, 0 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 469 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=853, Invalid=2569, Unknown=0, NotChecked=0, Total=3422 [2018-06-22 18:35:54,401 INFO ]: Start minimizeSevpa. Operand 43 states. [2018-06-22 18:35:54,405 INFO ]: Finished minimizeSevpa. Reduced states from 43 to 43. [2018-06-22 18:35:54,405 INFO ]: Start removeUnreachable. Operand 43 states. [2018-06-22 18:35:54,406 INFO ]: Finished removeUnreachable. Reduced from 43 states to 43 states and 44 transitions. [2018-06-22 18:35:54,406 INFO ]: Start accepts. Automaton has 43 states and 44 transitions. Word has length 69 [2018-06-22 18:35:54,406 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:54,406 INFO ]: Abstraction has 43 states and 44 transitions. [2018-06-22 18:35:54,406 INFO ]: Interpolant automaton has 42 states. [2018-06-22 18:35:54,406 INFO ]: Start isEmpty. Operand 43 states and 44 transitions. [2018-06-22 18:35:54,407 INFO ]: Finished isEmpty. Found accepting run of length 74 [2018-06-22 18:35:54,407 INFO ]: Found error trace [2018-06-22 18:35:54,407 INFO ]: trace histogram [17, 16, 16, 16, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:54,407 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:54,407 INFO ]: Analyzing trace with hash -787191579, now seen corresponding path program 16 times [2018-06-22 18:35:54,407 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:54,407 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:54,408 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:54,408 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:35:54,409 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:54,455 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:55,149 INFO ]: Checked inductivity of 528 backedges. 12 proven. 322 refuted. 0 times theorem prover too weak. 194 trivial. 0 not checked. [2018-06-22 18:35:55,149 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:55,149 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:55,155 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 18:35:55,322 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 18:35:55,322 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:55,331 INFO ]: Computing forward predicates... [2018-06-22 18:35:55,989 WARN ]: Spent 217.00 ms on a formula simplification. DAG size of input: 7 DAG size of output: 5 [2018-06-22 18:35:56,580 WARN ]: Spent 191.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 8 [2018-06-22 18:35:57,272 INFO ]: Checked inductivity of 528 backedges. 0 proven. 314 refuted. 0 times theorem prover too weak. 214 trivial. 0 not checked. [2018-06-22 18:35:57,293 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:35:57,293 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 44 [2018-06-22 18:35:57,293 INFO ]: Interpolant automaton has 44 states [2018-06-22 18:35:57,293 INFO ]: Constructing interpolant automaton starting with 44 interpolants. [2018-06-22 18:35:57,294 INFO ]: CoverageRelationStatistics Valid=441, Invalid=1451, Unknown=0, NotChecked=0, Total=1892 [2018-06-22 18:35:57,294 INFO ]: Start difference. First operand 43 states and 44 transitions. Second operand 44 states. [2018-06-22 18:35:58,242 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:35:58,242 INFO ]: Finished difference Result 45 states and 46 transitions. [2018-06-22 18:35:58,243 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-06-22 18:35:58,243 INFO ]: Start accepts. Automaton has 44 states. Word has length 73 [2018-06-22 18:35:58,244 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:35:58,244 INFO ]: With dead ends: 45 [2018-06-22 18:35:58,244 INFO ]: Without dead ends: 45 [2018-06-22 18:35:58,245 INFO ]: 0 DeclaredPredicates, 126 GetRequests, 66 SyntacticMatches, 0 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 444 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=1028, Invalid=2754, Unknown=0, NotChecked=0, Total=3782 [2018-06-22 18:35:58,245 INFO ]: Start minimizeSevpa. Operand 45 states. [2018-06-22 18:35:58,249 INFO ]: Finished minimizeSevpa. Reduced states from 45 to 45. [2018-06-22 18:35:58,249 INFO ]: Start removeUnreachable. Operand 45 states. [2018-06-22 18:35:58,250 INFO ]: Finished removeUnreachable. Reduced from 45 states to 45 states and 46 transitions. [2018-06-22 18:35:58,250 INFO ]: Start accepts. Automaton has 45 states and 46 transitions. Word has length 73 [2018-06-22 18:35:58,250 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:35:58,250 INFO ]: Abstraction has 45 states and 46 transitions. [2018-06-22 18:35:58,250 INFO ]: Interpolant automaton has 44 states. [2018-06-22 18:35:58,250 INFO ]: Start isEmpty. Operand 45 states and 46 transitions. [2018-06-22 18:35:58,251 INFO ]: Finished isEmpty. Found accepting run of length 78 [2018-06-22 18:35:58,251 INFO ]: Found error trace [2018-06-22 18:35:58,251 INFO ]: trace histogram [18, 17, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:35:58,251 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:35:58,251 INFO ]: Analyzing trace with hash 2070177031, now seen corresponding path program 17 times [2018-06-22 18:35:58,251 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:35:58,251 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:35:58,252 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:58,252 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:35:58,252 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:35:58,295 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:59,102 INFO ]: Checked inductivity of 595 backedges. 39 proven. 352 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2018-06-22 18:35:59,102 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:35:59,102 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:35:59,108 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 18:35:59,397 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 18 check-sat command(s) [2018-06-22 18:35:59,397 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:35:59,409 INFO ]: Computing forward predicates... [2018-06-22 18:36:00,043 INFO ]: Checked inductivity of 595 backedges. 12 proven. 393 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2018-06-22 18:36:00,063 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:36:00,063 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 26] total 46 [2018-06-22 18:36:00,064 INFO ]: Interpolant automaton has 46 states [2018-06-22 18:36:00,064 INFO ]: Constructing interpolant automaton starting with 46 interpolants. [2018-06-22 18:36:00,064 INFO ]: CoverageRelationStatistics Valid=315, Invalid=1755, Unknown=0, NotChecked=0, Total=2070 [2018-06-22 18:36:00,064 INFO ]: Start difference. First operand 45 states and 46 transitions. Second operand 46 states. [2018-06-22 18:36:01,434 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:36:01,435 INFO ]: Finished difference Result 47 states and 48 transitions. [2018-06-22 18:36:01,441 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-06-22 18:36:01,441 INFO ]: Start accepts. Automaton has 46 states. Word has length 77 [2018-06-22 18:36:01,441 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:36:01,442 INFO ]: With dead ends: 47 [2018-06-22 18:36:01,442 INFO ]: Without dead ends: 47 [2018-06-22 18:36:01,443 INFO ]: 0 DeclaredPredicates, 133 GetRequests, 69 SyntacticMatches, 1 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 646 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=981, Invalid=3179, Unknown=0, NotChecked=0, Total=4160 [2018-06-22 18:36:01,443 INFO ]: Start minimizeSevpa. Operand 47 states. [2018-06-22 18:36:01,451 INFO ]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-06-22 18:36:01,451 INFO ]: Start removeUnreachable. Operand 47 states. [2018-06-22 18:36:01,452 INFO ]: Finished removeUnreachable. Reduced from 47 states to 47 states and 48 transitions. [2018-06-22 18:36:01,452 INFO ]: Start accepts. Automaton has 47 states and 48 transitions. Word has length 77 [2018-06-22 18:36:01,452 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:36:01,452 INFO ]: Abstraction has 47 states and 48 transitions. [2018-06-22 18:36:01,452 INFO ]: Interpolant automaton has 46 states. [2018-06-22 18:36:01,452 INFO ]: Start isEmpty. Operand 47 states and 48 transitions. [2018-06-22 18:36:01,453 INFO ]: Finished isEmpty. Found accepting run of length 82 [2018-06-22 18:36:01,453 INFO ]: Found error trace [2018-06-22 18:36:01,453 INFO ]: trace histogram [19, 18, 18, 18, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:36:01,453 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:36:01,453 INFO ]: Analyzing trace with hash -430289751, now seen corresponding path program 18 times [2018-06-22 18:36:01,453 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:36:01,453 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:36:01,454 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:36:01,454 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:36:01,454 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:36:01,503 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:36:02,098 WARN ]: Spent 376.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 [2018-06-22 18:36:02,825 INFO ]: Checked inductivity of 666 backedges. 31 proven. 399 refuted. 0 times theorem prover too weak. 236 trivial. 0 not checked. [2018-06-22 18:36:02,825 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:36:02,825 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:36:02,832 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 18:36:03,180 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 19 check-sat command(s) [2018-06-22 18:36:03,180 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:36:03,190 INFO ]: Computing forward predicates... [2018-06-22 18:36:04,109 INFO ]: Checked inductivity of 666 backedges. 0 proven. 452 refuted. 0 times theorem prover too weak. 214 trivial. 0 not checked. [2018-06-22 18:36:04,131 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:36:04,131 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 27] total 49 [2018-06-22 18:36:04,131 INFO ]: Interpolant automaton has 49 states [2018-06-22 18:36:04,132 INFO ]: Constructing interpolant automaton starting with 49 interpolants. [2018-06-22 18:36:04,132 INFO ]: CoverageRelationStatistics Valid=416, Invalid=1936, Unknown=0, NotChecked=0, Total=2352 [2018-06-22 18:36:04,132 INFO ]: Start difference. First operand 47 states and 48 transitions. Second operand 49 states. [2018-06-22 18:36:05,413 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:36:05,413 INFO ]: Finished difference Result 49 states and 50 transitions. [2018-06-22 18:36:05,413 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-06-22 18:36:05,413 INFO ]: Start accepts. Automaton has 49 states. Word has length 81 [2018-06-22 18:36:05,413 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:36:05,414 INFO ]: With dead ends: 49 [2018-06-22 18:36:05,414 INFO ]: Without dead ends: 49 [2018-06-22 18:36:05,415 INFO ]: 0 DeclaredPredicates, 140 GetRequests, 73 SyntacticMatches, 0 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 686 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=1148, Invalid=3544, Unknown=0, NotChecked=0, Total=4692 [2018-06-22 18:36:05,415 INFO ]: Start minimizeSevpa. Operand 49 states. [2018-06-22 18:36:05,421 INFO ]: Finished minimizeSevpa. Reduced states from 49 to 49. [2018-06-22 18:36:05,421 INFO ]: Start removeUnreachable. Operand 49 states. [2018-06-22 18:36:05,422 INFO ]: Finished removeUnreachable. Reduced from 49 states to 49 states and 50 transitions. [2018-06-22 18:36:05,422 INFO ]: Start accepts. Automaton has 49 states and 50 transitions. Word has length 81 [2018-06-22 18:36:05,422 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:36:05,422 INFO ]: Abstraction has 49 states and 50 transitions. [2018-06-22 18:36:05,422 INFO ]: Interpolant automaton has 49 states. [2018-06-22 18:36:05,422 INFO ]: Start isEmpty. Operand 49 states and 50 transitions. [2018-06-22 18:36:05,423 INFO ]: Finished isEmpty. Found accepting run of length 86 [2018-06-22 18:36:05,423 INFO ]: Found error trace [2018-06-22 18:36:05,423 INFO ]: trace histogram [20, 19, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:36:05,423 INFO ]: === Iteration 20 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:36:05,423 INFO ]: Analyzing trace with hash -132956213, now seen corresponding path program 19 times [2018-06-22 18:36:05,423 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:36:05,423 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:36:05,424 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:36:05,424 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:36:05,424 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:36:05,471 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:36:05,976 WARN ]: Spent 302.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 [2018-06-22 18:36:06,273 WARN ]: Spent 161.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 21 [2018-06-22 18:36:07,048 INFO ]: Checked inductivity of 741 backedges. 40 proven. 441 refuted. 0 times theorem prover too weak. 260 trivial. 0 not checked. [2018-06-22 18:36:07,048 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:36:07,048 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:36:07,054 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:36:07,245 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:36:07,254 INFO ]: Computing forward predicates... [2018-06-22 18:36:08,452 INFO ]: Checked inductivity of 741 backedges. 0 proven. 398 refuted. 0 times theorem prover too weak. 343 trivial. 0 not checked. [2018-06-22 18:36:08,472 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:36:08,472 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 25] total 48 [2018-06-22 18:36:08,472 INFO ]: Interpolant automaton has 48 states [2018-06-22 18:36:08,472 INFO ]: Constructing interpolant automaton starting with 48 interpolants. [2018-06-22 18:36:08,473 INFO ]: CoverageRelationStatistics Valid=615, Invalid=1641, Unknown=0, NotChecked=0, Total=2256 [2018-06-22 18:36:08,473 INFO ]: Start difference. First operand 49 states and 50 transitions. Second operand 48 states. [2018-06-22 18:36:09,596 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:36:09,596 INFO ]: Finished difference Result 51 states and 52 transitions. [2018-06-22 18:36:09,596 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-06-22 18:36:09,596 INFO ]: Start accepts. Automaton has 48 states. Word has length 85 [2018-06-22 18:36:09,596 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:36:09,597 INFO ]: With dead ends: 51 [2018-06-22 18:36:09,597 INFO ]: Without dead ends: 51 [2018-06-22 18:36:09,598 INFO ]: 0 DeclaredPredicates, 147 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 518 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=1352, Invalid=3340, Unknown=0, NotChecked=0, Total=4692 [2018-06-22 18:36:09,598 INFO ]: Start minimizeSevpa. Operand 51 states. [2018-06-22 18:36:09,602 INFO ]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-06-22 18:36:09,602 INFO ]: Start removeUnreachable. Operand 51 states. [2018-06-22 18:36:09,602 INFO ]: Finished removeUnreachable. Reduced from 51 states to 51 states and 52 transitions. [2018-06-22 18:36:09,602 INFO ]: Start accepts. Automaton has 51 states and 52 transitions. Word has length 85 [2018-06-22 18:36:09,602 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:36:09,603 INFO ]: Abstraction has 51 states and 52 transitions. [2018-06-22 18:36:09,603 INFO ]: Interpolant automaton has 48 states. [2018-06-22 18:36:09,603 INFO ]: Start isEmpty. Operand 51 states and 52 transitions. [2018-06-22 18:36:09,603 INFO ]: Finished isEmpty. Found accepting run of length 90 [2018-06-22 18:36:09,603 INFO ]: Found error trace [2018-06-22 18:36:09,603 INFO ]: trace histogram [21, 20, 20, 20, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:36:09,604 INFO ]: === Iteration 21 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:36:09,604 INFO ]: Analyzing trace with hash 2128895597, now seen corresponding path program 20 times [2018-06-22 18:36:09,604 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:36:09,604 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:36:09,604 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:36:09,604 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:36:09,604 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:36:09,656 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:36:10,289 WARN ]: Spent 391.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 [2018-06-22 18:36:10,578 WARN ]: Spent 205.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-22 18:36:11,197 INFO ]: Checked inductivity of 820 backedges. 45 proven. 484 refuted. 0 times theorem prover too weak. 291 trivial. 0 not checked. [2018-06-22 18:36:11,197 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:36:11,198 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:36:11,204 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 18:36:11,409 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 18:36:11,409 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:36:11,419 INFO ]: Computing forward predicates... [2018-06-22 18:36:12,085 INFO ]: Checked inductivity of 820 backedges. 0 proven. 439 refuted. 0 times theorem prover too weak. 381 trivial. 0 not checked. [2018-06-22 18:36:12,105 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:36:12,105 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 26] total 50 [2018-06-22 18:36:12,106 INFO ]: Interpolant automaton has 50 states [2018-06-22 18:36:12,106 INFO ]: Constructing interpolant automaton starting with 50 interpolants. [2018-06-22 18:36:12,106 INFO ]: CoverageRelationStatistics Valid=676, Invalid=1774, Unknown=0, NotChecked=0, Total=2450 [2018-06-22 18:36:12,107 INFO ]: Start difference. First operand 51 states and 52 transitions. Second operand 50 states. [2018-06-22 18:36:13,228 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:36:13,228 INFO ]: Finished difference Result 53 states and 54 transitions. [2018-06-22 18:36:13,228 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-06-22 18:36:13,228 INFO ]: Start accepts. Automaton has 50 states. Word has length 89 [2018-06-22 18:36:13,228 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:36:13,229 INFO ]: With dead ends: 53 [2018-06-22 18:36:13,229 INFO ]: Without dead ends: 53 [2018-06-22 18:36:13,229 INFO ]: 0 DeclaredPredicates, 154 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 70 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 565 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=1481, Invalid=3631, Unknown=0, NotChecked=0, Total=5112 [2018-06-22 18:36:13,229 INFO ]: Start minimizeSevpa. Operand 53 states. [2018-06-22 18:36:13,234 INFO ]: Finished minimizeSevpa. Reduced states from 53 to 53. [2018-06-22 18:36:13,234 INFO ]: Start removeUnreachable. Operand 53 states. [2018-06-22 18:36:13,235 INFO ]: Finished removeUnreachable. Reduced from 53 states to 53 states and 54 transitions. [2018-06-22 18:36:13,235 INFO ]: Start accepts. Automaton has 53 states and 54 transitions. Word has length 89 [2018-06-22 18:36:13,235 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:36:13,235 INFO ]: Abstraction has 53 states and 54 transitions. [2018-06-22 18:36:13,235 INFO ]: Interpolant automaton has 50 states. [2018-06-22 18:36:13,235 INFO ]: Start isEmpty. Operand 53 states and 54 transitions. [2018-06-22 18:36:13,236 INFO ]: Finished isEmpty. Found accepting run of length 94 [2018-06-22 18:36:13,236 INFO ]: Found error trace [2018-06-22 18:36:13,236 INFO ]: trace histogram [22, 21, 21, 21, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:36:13,236 INFO ]: === Iteration 22 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:36:13,236 INFO ]: Analyzing trace with hash -2091202417, now seen corresponding path program 21 times [2018-06-22 18:36:13,236 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:36:13,236 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:36:13,237 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:36:13,237 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:36:13,237 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:36:13,289 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:36:14,176 INFO ]: Checked inductivity of 903 backedges. 63 proven. 526 refuted. 0 times theorem prover too weak. 314 trivial. 0 not checked. [2018-06-22 18:36:14,176 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:36:14,176 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:36:14,186 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 18:36:14,606 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 22 check-sat command(s) [2018-06-22 18:36:14,606 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:36:14,616 INFO ]: Computing forward predicates... [2018-06-22 18:36:15,880 INFO ]: Checked inductivity of 903 backedges. 14 proven. 591 refuted. 0 times theorem prover too weak. 298 trivial. 0 not checked. [2018-06-22 18:36:15,904 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:36:15,904 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 30] total 55 [2018-06-22 18:36:15,904 INFO ]: Interpolant automaton has 55 states [2018-06-22 18:36:15,904 INFO ]: Constructing interpolant automaton starting with 55 interpolants. [2018-06-22 18:36:15,905 INFO ]: CoverageRelationStatistics Valid=586, Invalid=2384, Unknown=0, NotChecked=0, Total=2970 [2018-06-22 18:36:15,905 INFO ]: Start difference. First operand 53 states and 54 transitions. Second operand 55 states. [2018-06-22 18:36:17,601 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:36:17,602 INFO ]: Finished difference Result 55 states and 56 transitions. [2018-06-22 18:36:17,606 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-06-22 18:36:17,606 INFO ]: Start accepts. Automaton has 55 states. Word has length 93 [2018-06-22 18:36:17,606 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:36:17,606 INFO ]: With dead ends: 55 [2018-06-22 18:36:17,606 INFO ]: Without dead ends: 55 [2018-06-22 18:36:17,607 INFO ]: 0 DeclaredPredicates, 161 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 76 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 870 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=1531, Invalid=4475, Unknown=0, NotChecked=0, Total=6006 [2018-06-22 18:36:17,607 INFO ]: Start minimizeSevpa. Operand 55 states. [2018-06-22 18:36:17,611 INFO ]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-06-22 18:36:17,611 INFO ]: Start removeUnreachable. Operand 55 states. [2018-06-22 18:36:17,611 INFO ]: Finished removeUnreachable. Reduced from 55 states to 55 states and 56 transitions. [2018-06-22 18:36:17,611 INFO ]: Start accepts. Automaton has 55 states and 56 transitions. Word has length 93 [2018-06-22 18:36:17,612 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:36:17,612 INFO ]: Abstraction has 55 states and 56 transitions. [2018-06-22 18:36:17,612 INFO ]: Interpolant automaton has 55 states. [2018-06-22 18:36:17,612 INFO ]: Start isEmpty. Operand 55 states and 56 transitions. [2018-06-22 18:36:17,613 INFO ]: Finished isEmpty. Found accepting run of length 98 [2018-06-22 18:36:17,613 INFO ]: Found error trace [2018-06-22 18:36:17,613 INFO ]: trace histogram [23, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:36:17,613 INFO ]: === Iteration 23 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:36:17,613 INFO ]: Analyzing trace with hash 440114737, now seen corresponding path program 22 times [2018-06-22 18:36:17,613 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:36:17,613 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:36:17,613 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:36:17,613 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 18:36:17,613 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:36:17,668 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:36:18,058 WARN ]: Spent 176.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 Received shutdown request... [2018-06-22 18:36:18,259 WARN ]: Removed 6 from assertion stack [2018-06-22 18:36:18,259 WARN ]: Verification canceled [2018-06-22 18:36:18,263 WARN ]: Timeout [2018-06-22 18:36:18,263 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 06:36:18 BoogieIcfgContainer [2018-06-22 18:36:18,263 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 18:36:18,264 INFO ]: Toolchain (without parser) took 56425.37 ms. Allocated memory was 308.3 MB in the beginning and 944.2 MB in the end (delta: 636.0 MB). Free memory was 258.7 MB in the beginning and 904.0 MB in the end (delta: -645.3 MB). Peak memory consumption was 583.3 MB. Max. memory is 3.6 GB. [2018-06-22 18:36:18,264 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.3 MB. Free memory is still 270.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 18:36:18,265 INFO ]: ChcToBoogie took 50.90 ms. Allocated memory is still 308.3 MB. Free memory was 258.7 MB in the beginning and 256.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 18:36:18,265 INFO ]: Boogie Preprocessor took 53.26 ms. Allocated memory is still 308.3 MB. Free memory was 256.7 MB in the beginning and 254.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 18:36:18,265 INFO ]: RCFGBuilder took 269.58 ms. Allocated memory is still 308.3 MB. Free memory was 254.7 MB in the beginning and 242.7 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 3.6 GB. [2018-06-22 18:36:18,266 INFO ]: TraceAbstraction took 56038.42 ms. Allocated memory was 308.3 MB in the beginning and 944.2 MB in the end (delta: 636.0 MB). Free memory was 242.7 MB in the beginning and 904.0 MB in the end (delta: -661.3 MB). Peak memory consumption was 567.4 MB. Max. memory is 3.6 GB. [2018-06-22 18:36:18,268 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 308.3 MB. Free memory is still 270.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 50.90 ms. Allocated memory is still 308.3 MB. Free memory was 258.7 MB in the beginning and 256.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 53.26 ms. Allocated memory is still 308.3 MB. Free memory was 256.7 MB in the beginning and 254.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 269.58 ms. Allocated memory is still 308.3 MB. Free memory was 254.7 MB in the beginning and 242.7 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 56038.42 ms. Allocated memory was 308.3 MB in the beginning and 944.2 MB in the end (delta: 636.0 MB). Free memory was 242.7 MB in the beginning and 904.0 MB in the end (delta: -661.3 MB). Peak memory consumption was 567.4 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 98 with TraceHistMax 23, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 15. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 55.9s OverallTime, 23 OverallIterations, 23 TraceHistogramMax, 17.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 242 SDtfs, 1691 SDslu, 2211 SDs, 0 SdLazy, 1822 SolverSat, 1876 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 3.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1914 GetRequests, 989 SyntacticMatches, 2 SemanticMatches, 923 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6435 ImplicationChecksByTransitivity, 40.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=55occurred in iteration=22, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 22 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.6s SsaConstructionTime, 3.7s SatisfiabilityAnalysisTime, 31.7s InterpolantComputationTime, 2235 NumberOfCodeBlocks, 2235 NumberOfCodeBlocksAsserted, 167 NumberOfCheckSat, 2192 ConstructedInterpolants, 0 QuantifiedInterpolants, 773624 SizeOfPredicates, 1050 NumberOfNonLiveVariables, 23835 ConjunctsInSsa, 1301 ConjunctsInUnsatCore, 43 InterpolantComputations, 1 PerfectInterpolantSequences, 5341/13706 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/Gas.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_18-36-18-277.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/Gas.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_18-36-18-277.csv Completed graceful shutdown