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/metros_4_e5_1150.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 19:26:04,737 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 19:26:04,739 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 19:26:04,750 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 19:26:04,750 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 19:26:04,751 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 19:26:04,752 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 19:26:04,753 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 19:26:04,755 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 19:26:04,755 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 19:26:04,756 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 19:26:04,756 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 19:26:04,757 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 19:26:04,758 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 19:26:04,761 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 19:26:04,761 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 19:26:04,763 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 19:26:04,766 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 19:26:04,767 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 19:26:04,768 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 19:26:04,769 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 19:26:04,772 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 19:26:04,772 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 19:26:04,772 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 19:26:04,773 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 19:26:04,774 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 19:26:04,775 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 19:26:04,775 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 19:26:04,777 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 19:26:04,777 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 19:26:04,777 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 19:26:04,778 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 19:26:04,778 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 19:26:04,779 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 19:26:04,780 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 19:26:04,780 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 19:26:04,794 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 19:26:04,794 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 19:26:04,794 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 19:26:04,795 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 19:26:04,795 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 19:26:04,796 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 19:26:04,796 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 19:26:04,796 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 19:26:04,796 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 19:26:04,796 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 19:26:04,797 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 19:26:04,797 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 19:26:04,797 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 19:26:04,797 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 19:26:04,797 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 19:26:04,797 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 19:26:04,798 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 19:26:04,798 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 19:26:04,798 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 19:26:04,799 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 19:26:04,799 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 19:26:04,839 INFO ]: Repository-Root is: /tmp [2018-06-22 19:26:04,853 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 19:26:04,860 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 19:26:04,862 INFO ]: Initializing SmtParser... [2018-06-22 19:26:04,862 INFO ]: SmtParser initialized [2018-06-22 19:26:04,863 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_4_e5_1150.smt2 [2018-06-22 19:26:04,864 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 19:26:04,957 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_4_e5_1150.smt2 unknown [2018-06-22 19:26:05,370 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_4_e5_1150.smt2 [2018-06-22 19:26:05,374 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 19:26:05,380 INFO ]: Walking toolchain with 4 elements. [2018-06-22 19:26:05,381 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 19:26:05,381 INFO ]: Initializing ChcToBoogie... [2018-06-22 19:26:05,381 INFO ]: ChcToBoogie initialized [2018-06-22 19:26:05,384 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 07:26:05" (1/1) ... [2018-06-22 19:26:05,451 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:26:05 Unit [2018-06-22 19:26:05,451 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 19:26:05,452 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 19:26:05,452 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 19:26:05,452 INFO ]: Boogie Preprocessor initialized [2018-06-22 19:26:05,473 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:26:05" (1/1) ... [2018-06-22 19:26:05,474 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:26:05" (1/1) ... [2018-06-22 19:26:05,483 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:26:05" (1/1) ... [2018-06-22 19:26:05,483 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:26:05" (1/1) ... [2018-06-22 19:26:05,493 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:26:05" (1/1) ... [2018-06-22 19:26:05,494 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:26:05" (1/1) ... [2018-06-22 19:26:05,496 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:26:05" (1/1) ... [2018-06-22 19:26:05,500 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 19:26:05,500 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 19:26:05,501 INFO ]: Initializing RCFGBuilder... [2018-06-22 19:26:05,501 INFO ]: RCFGBuilder initialized [2018-06-22 19:26:05,503 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:26:05" (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 19:26:05,517 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 19:26:05,517 INFO ]: Found specification of procedure False [2018-06-22 19:26:05,517 INFO ]: Found implementation of procedure False [2018-06-22 19:26:05,517 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 19:26:05,517 INFO ]: Found specification of procedure state [2018-06-22 19:26:05,517 INFO ]: Found implementation of procedure state [2018-06-22 19:26:05,517 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 19:26:05,517 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 19:26:05,517 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 19:26:05,875 INFO ]: Using library mode [2018-06-22 19:26:05,876 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 07:26:05 BoogieIcfgContainer [2018-06-22 19:26:05,876 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 19:26:05,879 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 19:26:05,880 INFO ]: Initializing TraceAbstraction... [2018-06-22 19:26:05,883 INFO ]: TraceAbstraction initialized [2018-06-22 19:26:05,883 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 07:26:05" (1/3) ... [2018-06-22 19:26:05,884 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7df6028e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 07:26:05, skipping insertion in model container [2018-06-22 19:26:05,884 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:26:05" (2/3) ... [2018-06-22 19:26:05,884 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7df6028e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 07:26:05, skipping insertion in model container [2018-06-22 19:26:05,884 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 07:26:05" (3/3) ... [2018-06-22 19:26:05,888 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 19:26:05,897 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 19:26:05,908 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 19:26:05,957 INFO ]: Using default assertion order modulation [2018-06-22 19:26:05,957 INFO ]: Interprodecural is true [2018-06-22 19:26:05,958 INFO ]: Hoare is false [2018-06-22 19:26:05,958 INFO ]: Compute interpolants for FPandBP [2018-06-22 19:26:05,958 INFO ]: Backedges is TWOTRACK [2018-06-22 19:26:05,958 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 19:26:05,958 INFO ]: Difference is false [2018-06-22 19:26:05,958 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 19:26:05,958 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 19:26:05,977 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 19:26:05,993 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 19:26:05,993 INFO ]: Found error trace [2018-06-22 19:26:05,994 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:26:05,994 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:26:06,000 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 19:26:06,002 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:26:06,003 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:26:06,046 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:06,046 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:26:06,046 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:06,164 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:26:06,386 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 19:26:06,388 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 19:26:06,388 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 19:26:06,390 INFO ]: Interpolant automaton has 4 states [2018-06-22 19:26:06,406 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 19:26:06,406 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 19:26:06,409 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 19:26:06,549 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:26:06,549 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 19:26:06,550 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 19:26:06,551 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 19:26:06,551 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:26:06,561 INFO ]: With dead ends: 13 [2018-06-22 19:26:06,561 INFO ]: Without dead ends: 13 [2018-06-22 19:26:06,563 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 19:26:06,576 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 19:26:06,596 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 19:26:06,597 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 19:26:06,597 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 19:26:06,599 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 19:26:06,599 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:26:06,599 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 19:26:06,599 INFO ]: Interpolant automaton has 4 states. [2018-06-22 19:26:06,599 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 19:26:06,600 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 19:26:06,600 INFO ]: Found error trace [2018-06-22 19:26:06,600 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:26:06,600 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:26:06,600 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 19:26:06,601 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:26:06,601 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:26:06,601 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:06,601 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:26:06,601 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:06,701 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:26:06,929 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 19:26:06,929 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:26:06,929 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 19:26:06,937 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:26:07,064 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:26:07,074 INFO ]: Computing forward predicates... [2018-06-22 19:26:07,452 WARN ]: Spent 198.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 7 [2018-06-22 19:26:07,728 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 19:26:07,748 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:26:07,749 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 19:26:07,749 INFO ]: Interpolant automaton has 9 states [2018-06-22 19:26:07,749 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 19:26:07,749 INFO ]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-06-22 19:26:07,749 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 19:26:08,091 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:26:08,091 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 19:26:08,092 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 19:26:08,093 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 19:26:08,093 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:26:08,093 INFO ]: With dead ends: 15 [2018-06-22 19:26:08,093 INFO ]: Without dead ends: 15 [2018-06-22 19:26:08,094 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2018-06-22 19:26:08,094 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 19:26:08,099 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 19:26:08,099 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 19:26:08,100 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 19:26:08,100 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 19:26:08,100 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:26:08,100 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 19:26:08,100 INFO ]: Interpolant automaton has 9 states. [2018-06-22 19:26:08,100 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 19:26:08,100 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 19:26:08,101 INFO ]: Found error trace [2018-06-22 19:26:08,101 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:26:08,103 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:26:08,103 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 19:26:08,103 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:26:08,103 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:26:08,104 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:08,104 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:26:08,104 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:08,262 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:26:08,574 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 19:26:08,574 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:26:08,574 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) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 19:26:08,587 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 19:26:08,721 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 19:26:08,721 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:26:08,727 INFO ]: Computing forward predicates... [2018-06-22 19:26:09,079 WARN ]: Spent 165.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 7 [2018-06-22 19:26:09,504 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 8 [2018-06-22 19:26:09,681 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 19:26:09,701 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:26:09,701 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-22 19:26:09,702 INFO ]: Interpolant automaton has 13 states [2018-06-22 19:26:09,702 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 19:26:09,702 INFO ]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2018-06-22 19:26:09,702 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 13 states. [2018-06-22 19:26:10,075 WARN ]: Spent 201.00 ms on a formula simplification that was a NOOP. DAG size: 45 [2018-06-22 19:26:10,247 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:26:10,247 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 19:26:10,248 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 19:26:10,248 INFO ]: Start accepts. Automaton has 13 states. Word has length 17 [2018-06-22 19:26:10,248 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:26:10,249 INFO ]: With dead ends: 17 [2018-06-22 19:26:10,249 INFO ]: Without dead ends: 17 [2018-06-22 19:26:10,249 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=66, Invalid=206, Unknown=0, NotChecked=0, Total=272 [2018-06-22 19:26:10,249 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 19:26:10,252 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 19:26:10,252 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 19:26:10,253 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 19:26:10,253 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 19:26:10,253 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:26:10,253 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 19:26:10,253 INFO ]: Interpolant automaton has 13 states. [2018-06-22 19:26:10,253 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 19:26:10,254 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 19:26:10,254 INFO ]: Found error trace [2018-06-22 19:26:10,254 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:26:10,255 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:26:10,255 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 19:26:10,255 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:26:10,255 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:26:10,256 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:10,256 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:26:10,256 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:10,373 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:26:10,789 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 19:26:10,789 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:26:10,789 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 19:26:10,806 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 19:26:10,991 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 19:26:10,991 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:26:10,998 INFO ]: Computing forward predicates... [2018-06-22 19:26:11,374 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 19:26:11,399 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:26:11,399 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2018-06-22 19:26:11,399 INFO ]: Interpolant automaton has 17 states [2018-06-22 19:26:11,399 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 19:26:11,399 INFO ]: CoverageRelationStatistics Valid=38, Invalid=234, Unknown=0, NotChecked=0, Total=272 [2018-06-22 19:26:11,400 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 17 states. [2018-06-22 19:26:11,813 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:26:11,813 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 19:26:11,814 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 19:26:11,814 INFO ]: Start accepts. Automaton has 17 states. Word has length 21 [2018-06-22 19:26:11,814 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:26:11,814 INFO ]: With dead ends: 19 [2018-06-22 19:26:11,814 INFO ]: Without dead ends: 19 [2018-06-22 19:26:11,815 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=98, Invalid=364, Unknown=0, NotChecked=0, Total=462 [2018-06-22 19:26:11,815 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 19:26:11,818 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 19:26:11,818 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 19:26:11,818 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 19:26:11,818 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 19:26:11,819 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:26:11,819 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 19:26:11,819 INFO ]: Interpolant automaton has 17 states. [2018-06-22 19:26:11,819 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 19:26:11,819 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 19:26:11,819 INFO ]: Found error trace [2018-06-22 19:26:11,819 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:26:11,819 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:26:11,819 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 19:26:11,819 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:26:11,819 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:26:11,820 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:11,820 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:26:11,820 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:12,014 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:26:12,495 WARN ]: Spent 123.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 19:26:13,147 WARN ]: Spent 565.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 19 [2018-06-22 19:26:13,556 WARN ]: Spent 304.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 28 [2018-06-22 19:26:13,734 WARN ]: Spent 108.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 27 [2018-06-22 19:26:13,904 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 25 [2018-06-22 19:26:14,068 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 25 [2018-06-22 19:26:14,117 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 19:26:14,117 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:26:14,118 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 19:26:14,126 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 19:26:14,296 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 19:26:14,296 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:26:14,306 INFO ]: Computing forward predicates... [2018-06-22 19:26:15,004 INFO ]: Checked inductivity of 36 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-06-22 19:26:15,025 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:26:15,025 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 20 [2018-06-22 19:26:15,025 INFO ]: Interpolant automaton has 20 states [2018-06-22 19:26:15,025 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 19:26:15,025 INFO ]: CoverageRelationStatistics Valid=46, Invalid=334, Unknown=0, NotChecked=0, Total=380 [2018-06-22 19:26:15,025 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 20 states. [2018-06-22 19:26:15,200 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 58 [2018-06-22 19:26:15,369 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 67 [2018-06-22 19:26:15,526 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 68 [2018-06-22 19:26:15,850 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:26:15,850 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 19:26:15,851 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 19:26:15,851 INFO ]: Start accepts. Automaton has 20 states. Word has length 25 [2018-06-22 19:26:15,851 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:26:15,851 INFO ]: With dead ends: 21 [2018-06-22 19:26:15,851 INFO ]: Without dead ends: 21 [2018-06-22 19:26:15,852 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=132, Invalid=518, Unknown=0, NotChecked=0, Total=650 [2018-06-22 19:26:15,852 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 19:26:15,855 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 19:26:15,855 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 19:26:15,856 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 19:26:15,856 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 19:26:15,856 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:26:15,856 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 19:26:15,856 INFO ]: Interpolant automaton has 20 states. [2018-06-22 19:26:15,856 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 19:26:15,857 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 19:26:15,857 INFO ]: Found error trace [2018-06-22 19:26:15,857 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:26:15,857 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:26:15,858 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 19:26:15,858 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:26:15,858 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:26:15,858 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:15,858 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:26:15,858 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:16,115 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:26:16,930 WARN ]: Spent 112.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 19:26:18,250 WARN ]: Spent 1.22 s on a formula simplification. DAG size of input: 234 DAG size of output: 26 [2018-06-22 19:26:18,455 WARN ]: Spent 177.00 ms on a formula simplification. DAG size of input: 172 DAG size of output: 20 [2018-06-22 19:26:18,728 WARN ]: Spent 240.00 ms on a formula simplification. DAG size of input: 125 DAG size of output: 28 [2018-06-22 19:26:19,438 WARN ]: Spent 543.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 21 [2018-06-22 19:26:20,102 WARN ]: Spent 399.00 ms on a formula simplification. DAG size of input: 127 DAG size of output: 19 [2018-06-22 19:26:20,593 WARN ]: Spent 416.00 ms on a formula simplification. DAG size of input: 236 DAG size of output: 26 [2018-06-22 19:26:21,162 WARN ]: Spent 458.00 ms on a formula simplification. DAG size of input: 327 DAG size of output: 19 [2018-06-22 19:26:21,794 WARN ]: Spent 519.00 ms on a formula simplification. DAG size of input: 234 DAG size of output: 16 [2018-06-22 19:26:21,807 INFO ]: Checked inductivity of 55 backedges. 1 proven. 39 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 19:26:21,807 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:26:21,807 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 19:26:21,820 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 19:26:22,056 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 19:26:22,056 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:26:22,068 INFO ]: Computing forward predicates... [2018-06-22 19:26:22,449 WARN ]: Spent 108.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 16 [2018-06-22 19:26:22,796 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 19:26:22,817 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:26:22,817 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 25 [2018-06-22 19:26:22,818 INFO ]: Interpolant automaton has 25 states [2018-06-22 19:26:22,818 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-22 19:26:22,818 INFO ]: CoverageRelationStatistics Valid=57, Invalid=543, Unknown=0, NotChecked=0, Total=600 [2018-06-22 19:26:22,818 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 25 states. [2018-06-22 19:26:23,102 WARN ]: Spent 192.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 86 [2018-06-22 19:26:23,513 WARN ]: Spent 345.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 98 [2018-06-22 19:26:23,941 WARN ]: Spent 265.00 ms on a formula simplification. DAG size of input: 119 DAG size of output: 104 [2018-06-22 19:26:24,190 WARN ]: Spent 190.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 94 [2018-06-22 19:26:24,398 WARN ]: Spent 169.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 87 [2018-06-22 19:26:24,581 WARN ]: Spent 140.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 76 [2018-06-22 19:26:24,629 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:26:24,630 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 19:26:24,631 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 19:26:24,631 INFO ]: Start accepts. Automaton has 25 states. Word has length 29 [2018-06-22 19:26:24,631 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:26:24,632 INFO ]: With dead ends: 23 [2018-06-22 19:26:24,632 INFO ]: Without dead ends: 23 [2018-06-22 19:26:24,632 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 84 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=185, Invalid=807, Unknown=0, NotChecked=0, Total=992 [2018-06-22 19:26:24,632 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 19:26:24,636 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 19:26:24,636 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 19:26:24,636 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 19:26:24,636 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 19:26:24,637 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:26:24,637 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 19:26:24,637 INFO ]: Interpolant automaton has 25 states. [2018-06-22 19:26:24,637 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 19:26:24,637 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 19:26:24,637 INFO ]: Found error trace [2018-06-22 19:26:24,637 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:26:24,637 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:26:24,638 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-22 19:26:24,638 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:26:24,638 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:26:24,638 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:24,638 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:26:24,638 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:24,945 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:26:25,956 WARN ]: Spent 318.00 ms on a formula simplification. DAG size of input: 180 DAG size of output: 28 [2018-06-22 19:26:26,296 WARN ]: Spent 309.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 20 [2018-06-22 19:26:26,679 WARN ]: Spent 271.00 ms on a formula simplification. DAG size of input: 208 DAG size of output: 29 [2018-06-22 19:26:26,855 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 124 DAG size of output: 22 [2018-06-22 19:26:27,067 WARN ]: Spent 123.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 20 [2018-06-22 19:26:27,831 WARN ]: Spent 673.00 ms on a formula simplification. DAG size of input: 267 DAG size of output: 26 [2018-06-22 19:26:28,145 WARN ]: Spent 227.00 ms on a formula simplification. DAG size of input: 246 DAG size of output: 19 [2018-06-22 19:26:28,729 WARN ]: Spent 500.00 ms on a formula simplification. DAG size of input: 177 DAG size of output: 27 [2018-06-22 19:26:28,773 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 19:26:28,773 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:26:28,773 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 19:26:28,778 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 19:26:29,068 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 19:26:29,068 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:26:29,078 INFO ]: Computing forward predicates... [2018-06-22 19:26:29,634 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 19:26:29,665 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:26:29,665 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 29 [2018-06-22 19:26:29,665 INFO ]: Interpolant automaton has 29 states [2018-06-22 19:26:29,666 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-22 19:26:29,666 INFO ]: CoverageRelationStatistics Valid=70, Invalid=742, Unknown=0, NotChecked=0, Total=812 [2018-06-22 19:26:29,666 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 29 states. [2018-06-22 19:26:29,903 WARN ]: Spent 151.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 93 [2018-06-22 19:26:30,184 WARN ]: Spent 232.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 115 [2018-06-22 19:26:30,417 WARN ]: Spent 199.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 106 [2018-06-22 19:26:30,640 WARN ]: Spent 184.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 102 [2018-06-22 19:26:30,856 WARN ]: Spent 175.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 101 [2018-06-22 19:26:31,073 WARN ]: Spent 146.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 87 [2018-06-22 19:26:31,266 WARN ]: Spent 145.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 88 [2018-06-22 19:26:31,314 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:26:31,314 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 19:26:31,315 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 19:26:31,315 INFO ]: Start accepts. Automaton has 29 states. Word has length 33 [2018-06-22 19:26:31,315 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:26:31,316 INFO ]: With dead ends: 25 [2018-06-22 19:26:31,316 INFO ]: Without dead ends: 25 [2018-06-22 19:26:31,317 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 69 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=244, Invalid=1088, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 19:26:31,317 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 19:26:31,322 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 19:26:31,322 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 19:26:31,323 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 19:26:31,323 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 19:26:31,323 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:26:31,323 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 19:26:31,323 INFO ]: Interpolant automaton has 29 states. [2018-06-22 19:26:31,323 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 19:26:31,324 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 19:26:31,324 INFO ]: Found error trace [2018-06-22 19:26:31,324 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:26:31,324 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:26:31,324 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-22 19:26:31,324 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:26:31,324 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:26:31,326 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:31,326 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:26:31,326 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:26:32,892 INFO ]: Conjunction of SSA is unsat Received shutdown request... [2018-06-22 19:27:07,156 WARN ]: Removed 2 from assertion stack [2018-06-22 19:27:07,156 WARN ]: Verification canceled [2018-06-22 19:27:07,161 WARN ]: Timeout [2018-06-22 19:27:07,161 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 07:27:07 BoogieIcfgContainer [2018-06-22 19:27:07,161 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 19:27:07,162 INFO ]: Toolchain (without parser) took 61786.94 ms. Allocated memory was 309.3 MB in the beginning and 1.4 GB in the end (delta: 1.1 GB). Free memory was 251.4 MB in the beginning and 159.8 MB in the end (delta: 91.6 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 19:27:07,163 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 309.3 MB. Free memory is still 275.1 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 19:27:07,163 INFO ]: ChcToBoogie took 70.79 ms. Allocated memory is still 309.3 MB. Free memory was 251.4 MB in the beginning and 249.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 19:27:07,163 INFO ]: Boogie Preprocessor took 47.80 ms. Allocated memory is still 309.3 MB. Free memory was 249.4 MB in the beginning and 247.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 19:27:07,163 INFO ]: RCFGBuilder took 375.53 ms. Allocated memory is still 309.3 MB. Free memory was 247.4 MB in the beginning and 223.8 MB in the end (delta: 23.6 MB). Peak memory consumption was 23.6 MB. Max. memory is 3.6 GB. [2018-06-22 19:27:07,164 INFO ]: TraceAbstraction took 61281.62 ms. Allocated memory was 309.3 MB in the beginning and 1.4 GB in the end (delta: 1.1 GB). Free memory was 223.8 MB in the beginning and 159.8 MB in the end (delta: 64.0 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 19:27:07,168 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 309.3 MB. Free memory is still 275.1 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 70.79 ms. Allocated memory is still 309.3 MB. Free memory was 251.4 MB in the beginning and 249.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 47.80 ms. Allocated memory is still 309.3 MB. Free memory was 249.4 MB in the beginning and 247.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 375.53 ms. Allocated memory is still 309.3 MB. Free memory was 247.4 MB in the beginning and 223.8 MB in the end (delta: 23.6 MB). Peak memory consumption was 23.6 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61281.62 ms. Allocated memory was 309.3 MB in the beginning and 1.4 GB in the end (delta: 1.1 GB). Free memory was 223.8 MB in the beginning and 159.8 MB in the end (delta: 64.0 MB). Peak memory consumption was 1.3 GB. 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 38 with TraceHistMax 8, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 2582. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 61.2s OverallTime, 8 OverallIterations, 8 TraceHistogramMax, 5.7s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 76 SDtfs, 208 SDslu, 578 SDs, 0 SdLazy, 447 SolverSat, 268 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 234 GetRequests, 98 SyntacticMatches, 1 SemanticMatches, 135 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 238 ImplicationChecksByTransitivity, 18.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=25occurred in iteration=7, 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.0s AutomataMinimizationTime, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 2.0s SatisfiabilityAnalysisTime, 16.8s InterpolantComputationTime, 285 NumberOfCodeBlocks, 285 NumberOfCodeBlocksAsserted, 29 NumberOfCheckSat, 272 ConstructedInterpolants, 0 QuantifiedInterpolants, 67756 SizeOfPredicates, 215 NumberOfNonLiveVariables, 6039 ConjunctsInSsa, 294 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 114/406 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/metros_4_e5_1150.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_19-27-07-178.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/metros_4_e5_1150.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_19-27-07-178.csv Completed graceful shutdown