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_3_e3_1275_e4_164.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 19:14:17,878 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 19:14:17,880 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 19:14:17,894 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 19:14:17,895 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 19:14:17,896 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 19:14:17,897 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 19:14:17,901 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 19:14:17,902 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 19:14:17,903 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 19:14:17,904 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 19:14:17,904 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 19:14:17,905 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 19:14:17,906 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 19:14:17,907 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 19:14:17,908 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 19:14:17,912 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 19:14:17,914 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 19:14:17,925 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 19:14:17,926 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 19:14:17,927 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 19:14:17,929 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 19:14:17,929 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 19:14:17,930 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 19:14:17,930 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 19:14:17,931 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 19:14:17,932 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 19:14:17,932 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 19:14:17,933 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 19:14:17,933 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 19:14:17,936 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 19:14:17,937 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 19:14:17,937 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 19:14:17,938 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 19:14:17,939 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 19:14:17,939 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:14:17,964 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 19:14:17,964 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 19:14:17,964 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 19:14:17,965 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 19:14:17,965 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 19:14:17,966 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 19:14:17,966 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 19:14:17,966 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 19:14:17,966 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 19:14:17,967 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 19:14:17,967 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 19:14:17,967 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 19:14:17,967 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 19:14:17,967 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 19:14:17,968 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 19:14:17,968 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 19:14:17,968 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 19:14:17,969 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 19:14:17,970 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 19:14:17,971 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 19:14:17,971 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 19:14:18,022 INFO ]: Repository-Root is: /tmp [2018-06-22 19:14:18,038 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 19:14:18,043 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 19:14:18,044 INFO ]: Initializing SmtParser... [2018-06-22 19:14:18,045 INFO ]: SmtParser initialized [2018-06-22 19:14:18,045 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_3_e3_1275_e4_164.smt2 [2018-06-22 19:14:18,046 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:14:18,140 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_3_e3_1275_e4_164.smt2 unknown [2018-06-22 19:14:18,596 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/metros_3_e3_1275_e4_164.smt2 [2018-06-22 19:14:18,601 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 19:14:18,606 INFO ]: Walking toolchain with 4 elements. [2018-06-22 19:14:18,606 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 19:14:18,607 INFO ]: Initializing ChcToBoogie... [2018-06-22 19:14:18,607 INFO ]: ChcToBoogie initialized [2018-06-22 19:14:18,610 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 07:14:18" (1/1) ... [2018-06-22 19:14:18,696 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:14:18 Unit [2018-06-22 19:14:18,696 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 19:14:18,697 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 19:14:18,697 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 19:14:18,697 INFO ]: Boogie Preprocessor initialized [2018-06-22 19:14:18,738 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:14:18" (1/1) ... [2018-06-22 19:14:18,738 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:14:18" (1/1) ... [2018-06-22 19:14:18,754 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:14:18" (1/1) ... [2018-06-22 19:14:18,755 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:14:18" (1/1) ... [2018-06-22 19:14:18,761 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:14:18" (1/1) ... [2018-06-22 19:14:18,763 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:14:18" (1/1) ... [2018-06-22 19:14:18,765 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:14:18" (1/1) ... [2018-06-22 19:14:18,779 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 19:14:18,779 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 19:14:18,779 INFO ]: Initializing RCFGBuilder... [2018-06-22 19:14:18,779 INFO ]: RCFGBuilder initialized [2018-06-22 19:14:18,780 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:14:18" (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:14:18,800 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 19:14:18,800 INFO ]: Found specification of procedure False [2018-06-22 19:14:18,800 INFO ]: Found implementation of procedure False [2018-06-22 19:14:18,801 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 19:14:18,801 INFO ]: Found specification of procedure state [2018-06-22 19:14:18,801 INFO ]: Found implementation of procedure state [2018-06-22 19:14:18,801 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 19:14:18,801 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 19:14:18,801 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 19:14:19,080 INFO ]: Using library mode [2018-06-22 19:14:19,080 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 07:14:19 BoogieIcfgContainer [2018-06-22 19:14:19,080 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 19:14:19,082 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 19:14:19,082 INFO ]: Initializing TraceAbstraction... [2018-06-22 19:14:19,085 INFO ]: TraceAbstraction initialized [2018-06-22 19:14:19,085 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 07:14:18" (1/3) ... [2018-06-22 19:14:19,086 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@778be343 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 07:14:19, skipping insertion in model container [2018-06-22 19:14:19,086 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 07:14:18" (2/3) ... [2018-06-22 19:14:19,086 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@778be343 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 07:14:19, skipping insertion in model container [2018-06-22 19:14:19,086 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 07:14:19" (3/3) ... [2018-06-22 19:14:19,088 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 19:14:19,098 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 19:14:19,111 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 19:14:19,161 INFO ]: Using default assertion order modulation [2018-06-22 19:14:19,162 INFO ]: Interprodecural is true [2018-06-22 19:14:19,162 INFO ]: Hoare is false [2018-06-22 19:14:19,162 INFO ]: Compute interpolants for FPandBP [2018-06-22 19:14:19,162 INFO ]: Backedges is TWOTRACK [2018-06-22 19:14:19,162 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 19:14:19,162 INFO ]: Difference is false [2018-06-22 19:14:19,162 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 19:14:19,162 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 19:14:19,183 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 19:14:19,195 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 19:14:19,195 INFO ]: Found error trace [2018-06-22 19:14:19,196 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:14:19,196 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:14:19,202 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 19:14:19,204 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:14:19,204 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:14:19,247 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:14:19,247 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:14:19,247 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:14:19,365 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:14:19,509 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:14:19,511 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 19:14:19,511 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 19:14:19,513 INFO ]: Interpolant automaton has 4 states [2018-06-22 19:14:19,527 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 19:14:19,528 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 19:14:19,529 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 19:14:19,682 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:14:19,683 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 19:14:19,684 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 19:14:19,685 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 19:14:19,686 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:14:19,699 INFO ]: With dead ends: 13 [2018-06-22 19:14:19,699 INFO ]: Without dead ends: 13 [2018-06-22 19:14:19,700 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 19:14:19,716 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 19:14:19,750 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 19:14:19,751 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 19:14:19,752 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 19:14:19,752 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 19:14:19,753 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:14:19,753 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 19:14:19,753 INFO ]: Interpolant automaton has 4 states. [2018-06-22 19:14:19,753 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 19:14:19,754 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 19:14:19,754 INFO ]: Found error trace [2018-06-22 19:14:19,754 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:14:19,754 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:14:19,754 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 19:14:19,754 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:14:19,754 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:14:19,755 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:14:19,755 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:14:19,755 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:14:19,831 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:14:20,184 WARN ]: Spent 101.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 19:14:20,306 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:14:20,306 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:14:20,306 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:14:20,316 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:14:20,429 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:14:20,440 INFO ]: Computing forward predicates... [2018-06-22 19:14:20,847 WARN ]: Spent 219.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 7 [2018-06-22 19:14:21,264 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:14:21,285 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:14:21,285 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 19:14:21,286 INFO ]: Interpolant automaton has 9 states [2018-06-22 19:14:21,286 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 19:14:21,286 INFO ]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-06-22 19:14:21,286 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 19:14:21,842 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:14:21,842 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 19:14:21,878 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 19:14:21,878 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 19:14:21,879 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:14:21,879 INFO ]: With dead ends: 15 [2018-06-22 19:14:21,879 INFO ]: Without dead ends: 15 [2018-06-22 19:14:21,880 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2018-06-22 19:14:21,880 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 19:14:21,882 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 19:14:21,882 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 19:14:21,883 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 19:14:21,883 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 19:14:21,883 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:14:21,883 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 19:14:21,883 INFO ]: Interpolant automaton has 9 states. [2018-06-22 19:14:21,883 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 19:14:21,884 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 19:14:21,889 INFO ]: Found error trace [2018-06-22 19:14:21,889 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:14:21,889 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:14:21,889 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 19:14:21,889 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:14:21,889 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:14:21,890 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:14:21,890 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 19:14:21,890 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:14:22,040 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:14:22,371 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:14:22,371 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:14:22,371 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:14:22,381 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 19:14:22,500 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 19:14:22,500 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:14:22,506 INFO ]: Computing forward predicates... [2018-06-22 19:14:22,917 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:14:22,951 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:14:22,951 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-22 19:14:22,951 INFO ]: Interpolant automaton has 13 states [2018-06-22 19:14:22,951 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 19:14:22,951 INFO ]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2018-06-22 19:14:22,952 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 13 states. [2018-06-22 19:14:23,277 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:14:23,277 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 19:14:23,278 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 19:14:23,278 INFO ]: Start accepts. Automaton has 13 states. Word has length 17 [2018-06-22 19:14:23,278 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:14:23,279 INFO ]: With dead ends: 19 [2018-06-22 19:14:23,279 INFO ]: Without dead ends: 19 [2018-06-22 19:14:23,279 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=78, Invalid=228, Unknown=0, NotChecked=0, Total=306 [2018-06-22 19:14:23,280 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 19:14:23,283 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 19:14:23,283 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 19:14:23,283 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 19:14:23,283 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 17 [2018-06-22 19:14:23,284 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:14:23,284 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 19:14:23,284 INFO ]: Interpolant automaton has 13 states. [2018-06-22 19:14:23,284 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 19:14:23,284 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 19:14:23,284 INFO ]: Found error trace [2018-06-22 19:14:23,284 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:14:23,285 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:14:23,285 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 3 times [2018-06-22 19:14:23,285 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:14:23,285 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:14:23,285 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:14:23,286 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:14:23,286 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:14:23,475 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:14:24,032 WARN ]: Spent 201.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 16 [2018-06-22 19:14:24,308 WARN ]: Spent 102.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 24 [2018-06-22 19:14:24,461 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 23 [2018-06-22 19:14:24,620 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 17 [2018-06-22 19:14:24,762 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 8 [2018-06-22 19:14:24,776 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:14:24,776 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:14:24,776 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) [2018-06-22 19:14:24,793 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 19:14:24,966 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-22 19:14:24,966 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:14:24,973 INFO ]: Computing forward predicates... [2018-06-22 19:14:25,323 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:14:25,345 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:14:25,345 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 21 [2018-06-22 19:14:25,346 INFO ]: Interpolant automaton has 21 states [2018-06-22 19:14:25,346 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 19:14:25,346 INFO ]: CoverageRelationStatistics Valid=46, Invalid=374, Unknown=0, NotChecked=0, Total=420 [2018-06-22 19:14:25,346 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 21 states. [2018-06-22 19:14:25,688 WARN ]: Spent 172.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 76 [2018-06-22 19:14:25,963 WARN ]: Spent 242.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 69 [2018-06-22 19:14:26,167 WARN ]: Spent 133.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 62 [2018-06-22 19:14:26,280 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:14:26,280 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 19:14:26,281 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 19:14:26,281 INFO ]: Start accepts. Automaton has 21 states. Word has length 25 [2018-06-22 19:14:26,281 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:14:26,282 INFO ]: With dead ends: 21 [2018-06-22 19:14:26,282 INFO ]: Without dead ends: 21 [2018-06-22 19:14:26,283 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=135, Invalid=567, Unknown=0, NotChecked=0, Total=702 [2018-06-22 19:14:26,283 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 19:14:26,286 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 19:14:26,286 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 19:14:26,287 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 19:14:26,287 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 19:14:26,287 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:14:26,287 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 19:14:26,287 INFO ]: Interpolant automaton has 21 states. [2018-06-22 19:14:26,287 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 19:14:26,288 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 19:14:26,288 INFO ]: Found error trace [2018-06-22 19:14:26,288 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:14:26,288 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:14:26,288 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 4 times [2018-06-22 19:14:26,288 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:14:26,288 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:14:26,289 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:14:26,289 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:14:26,289 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:14:26,650 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:14:27,196 WARN ]: Spent 114.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 19:14:27,447 WARN ]: Spent 192.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 24 [2018-06-22 19:14:27,831 WARN ]: Spent 361.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 23 [2018-06-22 19:14:28,013 WARN ]: Spent 112.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 20 [2018-06-22 19:14:28,289 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 16 [2018-06-22 19:14:28,557 WARN ]: Spent 225.00 ms on a formula simplification. DAG size of input: 157 DAG size of output: 23 [2018-06-22 19:14:28,764 WARN ]: Spent 177.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 20 [2018-06-22 19:14:28,779 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:14:28,779 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:14:28,779 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:14:28,789 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 19:14:28,977 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 19:14:28,977 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:14:28,985 INFO ]: Computing forward predicates... [2018-06-22 19:14:29,493 INFO ]: Checked inductivity of 55 backedges. 0 proven. 37 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-06-22 19:14:29,514 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:14:29,514 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12] total 23 [2018-06-22 19:14:29,515 INFO ]: Interpolant automaton has 23 states [2018-06-22 19:14:29,515 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 19:14:29,515 INFO ]: CoverageRelationStatistics Valid=57, Invalid=449, Unknown=0, NotChecked=0, Total=506 [2018-06-22 19:14:29,515 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 23 states. [2018-06-22 19:14:29,845 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 66 [2018-06-22 19:14:30,015 WARN ]: Spent 133.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 66 [2018-06-22 19:14:30,182 WARN ]: Spent 138.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 73 [2018-06-22 19:14:30,340 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 67 [2018-06-22 19:14:30,505 WARN ]: Spent 132.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 55 [2018-06-22 19:14:30,568 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:14:30,568 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 19:14:30,569 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 19:14:30,569 INFO ]: Start accepts. Automaton has 23 states. Word has length 29 [2018-06-22 19:14:30,570 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:14:30,570 INFO ]: With dead ends: 23 [2018-06-22 19:14:30,570 INFO ]: Without dead ends: 23 [2018-06-22 19:14:30,571 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 19 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=174, Invalid=696, Unknown=0, NotChecked=0, Total=870 [2018-06-22 19:14:30,571 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 19:14:30,577 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 19:14:30,577 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 19:14:30,577 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 19:14:30,577 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 19:14:30,578 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:14:30,578 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 19:14:30,578 INFO ]: Interpolant automaton has 23 states. [2018-06-22 19:14:30,578 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 19:14:30,578 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 19:14:30,578 INFO ]: Found error trace [2018-06-22 19:14:30,578 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:14:30,579 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:14:30,579 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 5 times [2018-06-22 19:14:30,579 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:14:30,579 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:14:30,579 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:14:30,579 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:14:30,579 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:14:30,991 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:14:32,986 WARN ]: Spent 113.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 19:14:36,300 WARN ]: Spent 3.07 s on a formula simplification. DAG size of input: 856 DAG size of output: 23 [2018-06-22 19:14:36,885 WARN ]: Spent 453.00 ms on a formula simplification. DAG size of input: 220 DAG size of output: 23 [2018-06-22 19:14:40,335 WARN ]: Spent 3.17 s on a formula simplification. DAG size of input: 408 DAG size of output: 18 [2018-06-22 19:14:41,996 WARN ]: Spent 1.46 s on a formula simplification. DAG size of input: 505 DAG size of output: 25 [2018-06-22 19:14:43,448 WARN ]: Spent 1.27 s on a formula simplification. DAG size of input: 551 DAG size of output: 25 [2018-06-22 19:14:45,432 WARN ]: Spent 1.69 s on a formula simplification. DAG size of input: 549 DAG size of output: 22 [2018-06-22 19:14:48,286 WARN ]: Spent 2.49 s on a formula simplification. DAG size of input: 940 DAG size of output: 24 [2018-06-22 19:14:51,528 WARN ]: Spent 2.88 s on a formula simplification. DAG size of input: 917 DAG size of output: 17 [2018-06-22 19:14:54,054 WARN ]: Spent 2.22 s on a formula simplification. DAG size of input: 680 DAG size of output: 16 [2018-06-22 19:14:58,629 WARN ]: Spent 4.12 s on a formula simplification. DAG size of input: 822 DAG size of output: 15 [2018-06-22 19:14:58,648 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:14:58,648 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 19:14:58,648 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:14:58,654 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 19:14:58,972 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2018-06-22 19:14:58,972 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:14:58,993 INFO ]: Computing forward predicates... [2018-06-22 19:14:59,526 INFO ]: Checked inductivity of 78 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2018-06-22 19:14:59,553 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 19:14:59,553 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 28 [2018-06-22 19:14:59,553 INFO ]: Interpolant automaton has 28 states [2018-06-22 19:14:59,554 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-22 19:14:59,554 INFO ]: CoverageRelationStatistics Valid=61, Invalid=695, Unknown=0, NotChecked=0, Total=756 [2018-06-22 19:14:59,554 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 28 states. [2018-06-22 19:14:59,774 WARN ]: Spent 167.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 85 [2018-06-22 19:15:00,072 WARN ]: Spent 221.00 ms on a formula simplification. DAG size of input: 121 DAG size of output: 95 [2018-06-22 19:15:00,395 WARN ]: Spent 241.00 ms on a formula simplification. DAG size of input: 129 DAG size of output: 103 [2018-06-22 19:15:00,659 WARN ]: Spent 217.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 104 [2018-06-22 19:15:00,894 WARN ]: Spent 196.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 96 [2018-06-22 19:15:01,113 WARN ]: Spent 176.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 86 [2018-06-22 19:15:01,315 WARN ]: Spent 151.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 75 [2018-06-22 19:15:01,371 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 19:15:01,371 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 19:15:01,372 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 19:15:01,372 INFO ]: Start accepts. Automaton has 28 states. Word has length 33 [2018-06-22 19:15:01,372 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 19:15:01,372 INFO ]: With dead ends: 25 [2018-06-22 19:15:01,372 INFO ]: Without dead ends: 25 [2018-06-22 19:15:01,373 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 21 SyntacticMatches, 1 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 26.9s TimeCoverageRelationStatistics Valid=224, Invalid=1036, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 19:15:01,373 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 19:15:01,377 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 19:15:01,377 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 19:15:01,378 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 19:15:01,378 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 19:15:01,378 INFO ]: Finished accepts. word is rejected. [2018-06-22 19:15:01,378 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 19:15:01,378 INFO ]: Interpolant automaton has 28 states. [2018-06-22 19:15:01,378 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 19:15:01,379 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 19:15:01,379 INFO ]: Found error trace [2018-06-22 19:15:01,379 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 19:15:01,379 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 19:15:01,379 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 6 times [2018-06-22 19:15:01,379 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 19:15:01,379 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 19:15:01,381 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:15:01,381 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 19:15:01,381 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 19:15:02,126 INFO ]: Conjunction of SSA is unsat [2018-06-22 19:15:05,275 WARN ]: Spent 120.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 19:15:22,117 WARN ]: Spent 15.86 s on a formula simplification. DAG size of input: 1467 DAG size of output: 24 Received shutdown request... [2018-06-22 19:15:23,460 WARN ]: Removed 2 from assertion stack [2018-06-22 19:15:23,461 WARN ]: Verification canceled [2018-06-22 19:15:23,464 WARN ]: Timeout [2018-06-22 19:15:23,464 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 07:15:23 BoogieIcfgContainer [2018-06-22 19:15:23,464 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 19:15:23,465 INFO ]: Toolchain (without parser) took 64863.70 ms. Allocated memory was 306.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 248.3 MB in the beginning and 1.1 GB in the end (delta: -844.4 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 19:15:23,465 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 306.7 MB. Free memory is still 272.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 19:15:23,465 INFO ]: ChcToBoogie took 89.87 ms. Allocated memory is still 306.7 MB. Free memory was 248.3 MB in the beginning and 246.3 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:15:23,466 INFO ]: Boogie Preprocessor took 82.14 ms. Allocated memory is still 306.7 MB. Free memory was 246.3 MB in the beginning and 244.3 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:15:23,466 INFO ]: RCFGBuilder took 300.95 ms. Allocated memory is still 306.7 MB. Free memory was 244.3 MB in the beginning and 220.3 MB in the end (delta: 24.0 MB). Peak memory consumption was 24.0 MB. Max. memory is 3.6 GB. [2018-06-22 19:15:23,466 INFO ]: TraceAbstraction took 64382.41 ms. Allocated memory was 306.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 220.3 MB in the beginning and 1.1 GB in the end (delta: -872.4 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 19:15:23,468 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.06 ms. Allocated memory is still 306.7 MB. Free memory is still 272.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 89.87 ms. Allocated memory is still 306.7 MB. Free memory was 248.3 MB in the beginning and 246.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 82.14 ms. Allocated memory is still 306.7 MB. Free memory was 246.3 MB in the beginning and 244.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 300.95 ms. Allocated memory is still 306.7 MB. Free memory was 244.3 MB in the beginning and 220.3 MB in the end (delta: 24.0 MB). Peak memory consumption was 24.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 64382.41 ms. Allocated memory was 306.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 220.3 MB in the beginning and 1.1 GB in the end (delta: -872.4 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 1109. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 64.3s OverallTime, 7 OverallIterations, 8 TraceHistogramMax, 4.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 67 SDtfs, 188 SDslu, 465 SDs, 0 SdLazy, 372 SolverSat, 242 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 200 GetRequests, 83 SyntacticMatches, 3 SemanticMatches, 114 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 204 ImplicationChecksByTransitivity, 33.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=25occurred in iteration=6, 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, 6 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 1.9s SatisfiabilityAnalysisTime, 34.7s InterpolantComputationTime, 243 NumberOfCodeBlocks, 243 NumberOfCodeBlocksAsserted, 23 NumberOfCheckSat, 232 ConstructedInterpolants, 0 QuantifiedInterpolants, 50844 SizeOfPredicates, 152 NumberOfNonLiveVariables, 5152 ConjunctsInSsa, 196 ConjunctsInUnsatCore, 11 InterpolantComputations, 1 PerfectInterpolantSequences, 104/364 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_3_e3_1275_e4_164.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_19-15-23-476.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/metros_3_e3_1275_e4_164.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_19-15-23-476.csv Completed graceful shutdown