java -Xss4m -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_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/bind_expands_vars2.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 12:47:00,138 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 12:47:00,140 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 12:47:00,153 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 12:47:00,154 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 12:47:00,155 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 12:47:00,156 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 12:47:00,158 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 12:47:00,160 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 12:47:00,160 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 12:47:00,161 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 12:47:00,162 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 12:47:00,162 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 12:47:00,165 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 12:47:00,166 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 12:47:00,167 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 12:47:00,169 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 12:47:00,171 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 12:47:00,174 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 12:47:00,175 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 12:47:00,176 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 12:47:00,178 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 12:47:00,178 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 12:47:00,179 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 12:47:00,180 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 12:47:00,180 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 12:47:00,181 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 12:47:00,182 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 12:47:00,183 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 12:47:00,183 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 12:47:00,184 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 12:47:00,185 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 12:47:00,185 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 12:47:00,186 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 12:47:00,186 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 12:47:00,187 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 12:47:00,201 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 12:47:00,202 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 12:47:00,202 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 12:47:00,202 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 12:47:00,203 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 12:47:00,204 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 12:47:00,204 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 12:47:00,204 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 12:47:00,204 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 12:47:00,204 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 12:47:00,205 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 12:47:00,205 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 12:47:00,208 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 12:47:00,208 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 12:47:00,208 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 12:47:00,208 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 12:47:00,208 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 12:47:00,209 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 12:47:00,209 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 12:47:00,209 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 12:47:00,209 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 12:47:00,211 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 12:47:00,211 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 12:47:00,270 INFO ]: Repository-Root is: /tmp [2018-06-25 12:47:00,292 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 12:47:00,297 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 12:47:00,298 INFO ]: Initializing SmtParser... [2018-06-25 12:47:00,299 INFO ]: SmtParser initialized [2018-06-25 12:47:00,299 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/bind_expands_vars2.c.smt2 [2018-06-25 12:47:00,301 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-25 12:47:00,396 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/bind_expands_vars2.c.smt2 unknown [2018-06-25 12:47:00,711 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/bind_expands_vars2.c.smt2 [2018-06-25 12:47:00,720 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 12:47:00,739 INFO ]: Walking toolchain with 4 elements. [2018-06-25 12:47:00,740 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 12:47:00,740 INFO ]: Initializing ChcToBoogie... [2018-06-25 12:47:00,740 INFO ]: ChcToBoogie initialized [2018-06-25 12:47:00,753 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:47:00" (1/1) ... [2018-06-25 12:47:00,816 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:47:00 Unit [2018-06-25 12:47:00,816 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 12:47:00,817 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 12:47:00,817 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 12:47:00,817 INFO ]: Boogie Preprocessor initialized [2018-06-25 12:47:00,835 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:47:00" (1/1) ... [2018-06-25 12:47:00,836 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:47:00" (1/1) ... [2018-06-25 12:47:00,841 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:47:00" (1/1) ... [2018-06-25 12:47:00,841 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:47:00" (1/1) ... [2018-06-25 12:47:00,844 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:47:00" (1/1) ... [2018-06-25 12:47:00,846 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:47:00" (1/1) ... [2018-06-25 12:47:00,851 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:47:00" (1/1) ... [2018-06-25 12:47:00,853 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 12:47:00,854 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 12:47:00,854 INFO ]: Initializing RCFGBuilder... [2018-06-25 12:47:00,854 INFO ]: RCFGBuilder initialized [2018-06-25 12:47:00,855 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:47:00" (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-25 12:47:00,872 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 12:47:00,872 INFO ]: Found specification of procedure gotoProc [2018-06-25 12:47:00,872 INFO ]: Found implementation of procedure gotoProc [2018-06-25 12:47:00,873 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 12:47:00,873 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 12:47:00,873 INFO ]: Found implementation of procedure Ultimate.START [2018-06-25 12:47:01,062 INFO ]: Using library mode [2018-06-25 12:47:01,062 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:47:01 BoogieIcfgContainer [2018-06-25 12:47:01,062 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 12:47:01,064 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 12:47:01,064 INFO ]: Initializing TraceAbstraction... [2018-06-25 12:47:01,067 INFO ]: TraceAbstraction initialized [2018-06-25 12:47:01,067 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:47:00" (1/3) ... [2018-06-25 12:47:01,068 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@54704120 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 12:47:01, skipping insertion in model container [2018-06-25 12:47:01,069 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:47:00" (2/3) ... [2018-06-25 12:47:01,069 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@54704120 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 12:47:01, skipping insertion in model container [2018-06-25 12:47:01,069 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:47:01" (3/3) ... [2018-06-25 12:47:01,074 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 12:47:01,082 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 12:47:01,089 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 12:47:01,130 INFO ]: Using default assertion order modulation [2018-06-25 12:47:01,130 INFO ]: Interprodecural is true [2018-06-25 12:47:01,130 INFO ]: Hoare is false [2018-06-25 12:47:01,130 INFO ]: Compute interpolants for FPandBP [2018-06-25 12:47:01,130 INFO ]: Backedges is TWOTRACK [2018-06-25 12:47:01,130 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 12:47:01,131 INFO ]: Difference is false [2018-06-25 12:47:01,131 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 12:47:01,131 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 12:47:01,143 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 12:47:01,156 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 12:47:01,157 INFO ]: Found error trace [2018-06-25 12:47:01,158 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:47:01,158 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:47:01,162 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 12:47:01,164 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:47:01,165 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:47:01,214 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:01,214 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:47:01,214 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:01,262 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:01,346 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:01,348 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 12:47:01,349 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 12:47:01,351 INFO ]: Interpolant automaton has 3 states [2018-06-25 12:47:01,367 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 12:47:01,368 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:47:01,371 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 12:47:01,444 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:47:01,445 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 12:47:01,445 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 12:47:01,447 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 12:47:01,447 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:47:01,460 INFO ]: With dead ends: 9 [2018-06-25 12:47:01,460 INFO ]: Without dead ends: 9 [2018-06-25 12:47:01,462 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:47:01,481 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 12:47:01,505 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 12:47:01,506 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 12:47:01,507 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 12:47:01,508 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 12:47:01,509 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:47:01,509 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 12:47:01,509 INFO ]: Interpolant automaton has 3 states. [2018-06-25 12:47:01,509 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 12:47:01,509 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 12:47:01,509 INFO ]: Found error trace [2018-06-25 12:47:01,509 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:47:01,509 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:47:01,509 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 12:47:01,510 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:47:01,510 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:47:01,510 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:01,510 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:47:01,510 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:01,539 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:01,684 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:01,684 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:47:01,684 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-25 12:47:01,698 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:47:01,745 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:01,753 INFO ]: Computing forward predicates... [2018-06-25 12:47:02,545 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:02,569 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:47:02,570 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 12:47:02,570 INFO ]: Interpolant automaton has 5 states [2018-06-25 12:47:02,570 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 12:47:02,570 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-25 12:47:02,571 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 12:47:02,789 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:47:02,789 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 12:47:02,789 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 12:47:02,789 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 12:47:02,789 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:47:02,790 INFO ]: With dead ends: 10 [2018-06-25 12:47:02,790 INFO ]: Without dead ends: 10 [2018-06-25 12:47:02,791 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-25 12:47:02,791 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 12:47:02,792 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 12:47:02,792 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 12:47:02,792 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 12:47:02,792 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 12:47:02,793 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:47:02,793 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 12:47:02,793 INFO ]: Interpolant automaton has 5 states. [2018-06-25 12:47:02,793 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 12:47:02,793 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 12:47:02,793 INFO ]: Found error trace [2018-06-25 12:47:02,793 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:47:02,793 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:47:02,794 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-25 12:47:02,794 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:47:02,794 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:47:02,795 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:02,795 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:47:02,795 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:02,848 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:03,079 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 5 [2018-06-25 12:47:03,095 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:03,095 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:47:03,095 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-25 12:47:03,103 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 12:47:03,151 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 12:47:03,152 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:03,154 INFO ]: Computing forward predicates... [2018-06-25 12:47:05,793 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:05,824 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:47:05,825 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-25 12:47:05,825 INFO ]: Interpolant automaton has 6 states [2018-06-25 12:47:05,825 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 12:47:05,825 INFO ]: CoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-25 12:47:05,825 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-25 12:47:05,938 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:47:05,938 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 12:47:05,939 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 12:47:05,939 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-25 12:47:05,939 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:47:05,939 INFO ]: With dead ends: 11 [2018-06-25 12:47:05,939 INFO ]: Without dead ends: 11 [2018-06-25 12:47:05,939 INFO ]: 0 DeclaredPredicates, 14 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2018-06-25 12:47:05,939 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 12:47:05,940 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 12:47:05,940 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 12:47:05,941 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 12:47:05,941 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 12:47:05,941 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:47:05,941 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 12:47:05,941 INFO ]: Interpolant automaton has 6 states. [2018-06-25 12:47:05,941 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 12:47:05,941 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 12:47:05,941 INFO ]: Found error trace [2018-06-25 12:47:05,941 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:47:05,942 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:47:05,942 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 3 times [2018-06-25 12:47:05,942 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:47:05,942 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:47:05,943 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:05,943 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:47:05,943 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:05,982 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:06,079 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:06,079 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:47:06,079 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-25 12:47:06,085 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 12:47:06,136 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 12:47:06,136 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:06,141 INFO ]: Computing forward predicates... [2018-06-25 12:47:07,146 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:47:10,618 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:10,656 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:47:10,656 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-25 12:47:10,656 INFO ]: Interpolant automaton has 7 states [2018-06-25 12:47:10,657 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 12:47:10,657 INFO ]: CoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2018-06-25 12:47:10,657 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-25 12:47:11,256 WARN ]: Spent 336.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 3 [2018-06-25 12:47:11,910 WARN ]: Spent 553.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 7 [2018-06-25 12:47:12,176 WARN ]: Spent 131.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 8 [2018-06-25 12:47:12,177 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:47:12,178 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 12:47:12,178 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 12:47:12,178 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-25 12:47:12,178 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:47:12,178 INFO ]: With dead ends: 12 [2018-06-25 12:47:12,178 INFO ]: Without dead ends: 12 [2018-06-25 12:47:12,179 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=42, Invalid=68, Unknown=0, NotChecked=0, Total=110 [2018-06-25 12:47:12,179 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 12:47:12,180 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 12:47:12,180 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 12:47:12,180 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 12:47:12,180 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 12:47:12,181 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:47:12,181 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 12:47:12,181 INFO ]: Interpolant automaton has 7 states. [2018-06-25 12:47:12,181 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 12:47:12,181 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 12:47:12,181 INFO ]: Found error trace [2018-06-25 12:47:12,181 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:47:12,181 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:47:12,181 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 4 times [2018-06-25 12:47:12,181 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:47:12,181 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:47:12,182 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:12,182 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:47:12,182 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:12,228 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:12,397 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:12,397 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:47:12,397 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-25 12:47:12,407 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 12:47:12,456 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 12:47:12,456 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:12,460 INFO ]: Computing forward predicates... [2018-06-25 12:47:18,147 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:18,168 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:47:18,168 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 8 [2018-06-25 12:47:18,169 INFO ]: Interpolant automaton has 8 states [2018-06-25 12:47:18,169 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-25 12:47:18,169 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-25 12:47:18,169 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 8 states. [2018-06-25 12:47:18,290 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:47:18,290 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-25 12:47:18,290 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-25 12:47:18,290 INFO ]: Start accepts. Automaton has 8 states. Word has length 11 [2018-06-25 12:47:18,290 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:47:18,291 INFO ]: With dead ends: 13 [2018-06-25 12:47:18,291 INFO ]: Without dead ends: 13 [2018-06-25 12:47:18,291 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=58, Invalid=98, Unknown=0, NotChecked=0, Total=156 [2018-06-25 12:47:18,291 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-25 12:47:18,292 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-25 12:47:18,292 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-25 12:47:18,292 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-25 12:47:18,292 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-25 12:47:18,292 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:47:18,292 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-25 12:47:18,292 INFO ]: Interpolant automaton has 8 states. [2018-06-25 12:47:18,292 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-25 12:47:18,292 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-25 12:47:18,292 INFO ]: Found error trace [2018-06-25 12:47:18,292 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:47:18,293 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:47:18,293 INFO ]: Analyzing trace with hash 1940481556, now seen corresponding path program 5 times [2018-06-25 12:47:18,293 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:47:18,293 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:47:18,293 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:18,293 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:47:18,293 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:18,361 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:18,776 WARN ]: Spent 234.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 4 [2018-06-25 12:47:18,833 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:18,833 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:47:18,833 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-25 12:47:18,841 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 12:47:18,949 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-25 12:47:18,949 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:18,953 INFO ]: Computing forward predicates... [2018-06-25 12:47:22,034 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:22,055 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:47:22,055 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2018-06-25 12:47:22,055 INFO ]: Interpolant automaton has 10 states [2018-06-25 12:47:22,055 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-25 12:47:22,055 INFO ]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2018-06-25 12:47:22,055 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 10 states. [2018-06-25 12:47:22,282 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:47:22,282 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-25 12:47:22,282 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-25 12:47:22,282 INFO ]: Start accepts. Automaton has 10 states. Word has length 12 [2018-06-25 12:47:22,282 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:47:22,282 INFO ]: With dead ends: 14 [2018-06-25 12:47:22,282 INFO ]: Without dead ends: 14 [2018-06-25 12:47:22,283 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 51 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=86, Invalid=154, Unknown=0, NotChecked=0, Total=240 [2018-06-25 12:47:22,283 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-25 12:47:22,286 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-25 12:47:22,286 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-25 12:47:22,287 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-25 12:47:22,287 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-25 12:47:22,287 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:47:22,287 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-25 12:47:22,287 INFO ]: Interpolant automaton has 10 states. [2018-06-25 12:47:22,287 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-25 12:47:22,287 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-25 12:47:22,287 INFO ]: Found error trace [2018-06-25 12:47:22,287 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:47:22,288 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:47:22,288 INFO ]: Analyzing trace with hash 23503628, now seen corresponding path program 6 times [2018-06-25 12:47:22,288 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:47:22,288 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:47:22,288 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:22,288 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:47:22,288 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:22,363 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:23,169 WARN ]: Spent 549.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 8 [2018-06-25 12:47:23,457 WARN ]: Spent 213.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 10 [2018-06-25 12:47:23,594 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:23,594 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:47:23,594 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-25 12:47:23,605 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 12:47:23,654 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-25 12:47:23,654 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:23,657 INFO ]: Computing forward predicates... [2018-06-25 12:47:27,497 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:27,517 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:47:27,517 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 11 [2018-06-25 12:47:27,517 INFO ]: Interpolant automaton has 11 states [2018-06-25 12:47:27,517 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-25 12:47:27,517 INFO ]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2018-06-25 12:47:27,517 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 11 states. [2018-06-25 12:47:27,667 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:47:27,667 INFO ]: Finished difference Result 15 states and 15 transitions. [2018-06-25 12:47:27,667 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-25 12:47:27,667 INFO ]: Start accepts. Automaton has 11 states. Word has length 13 [2018-06-25 12:47:27,667 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:47:27,667 INFO ]: With dead ends: 15 [2018-06-25 12:47:27,667 INFO ]: Without dead ends: 15 [2018-06-25 12:47:27,668 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 7 SyntacticMatches, 5 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 58 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=105, Invalid=201, Unknown=0, NotChecked=0, Total=306 [2018-06-25 12:47:27,668 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-25 12:47:27,669 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-25 12:47:27,669 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-25 12:47:27,670 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-06-25 12:47:27,671 INFO ]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 13 [2018-06-25 12:47:27,671 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:47:27,671 INFO ]: Abstraction has 15 states and 15 transitions. [2018-06-25 12:47:27,671 INFO ]: Interpolant automaton has 11 states. [2018-06-25 12:47:27,671 INFO ]: Start isEmpty. Operand 15 states and 15 transitions. [2018-06-25 12:47:27,671 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-25 12:47:27,671 INFO ]: Found error trace [2018-06-25 12:47:27,671 INFO ]: trace histogram [7, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:47:27,671 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:47:27,671 INFO ]: Analyzing trace with hash 726730004, now seen corresponding path program 7 times [2018-06-25 12:47:27,671 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:47:27,671 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:47:27,671 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:27,672 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:47:27,672 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:27,733 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:28,076 WARN ]: Spent 147.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2018-06-25 12:47:28,268 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:28,268 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:47:28,268 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:47:28,283 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:47:28,348 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:28,353 INFO ]: Computing forward predicates... [2018-06-25 12:47:28,962 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:47:30,931 WARN ]: Spent 658.00 ms on a formula simplification. DAG size of input: 620 DAG size of output: 24 [2018-06-25 12:47:35,600 WARN ]: Spent 740.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 25 [2018-06-25 12:47:38,177 WARN ]: Spent 1.14 s on a formula simplification. DAG size of input: 35 DAG size of output: 22 [2018-06-25 12:47:43,202 WARN ]: Spent 3.88 s on a formula simplification. DAG size of input: 64 DAG size of output: 20 [2018-06-25 12:47:45,398 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:45,422 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:47:45,422 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2018-06-25 12:47:45,422 INFO ]: Interpolant automaton has 15 states [2018-06-25 12:47:45,422 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-25 12:47:45,422 INFO ]: CoverageRelationStatistics Valid=54, Invalid=156, Unknown=0, NotChecked=0, Total=210 [2018-06-25 12:47:45,422 INFO ]: Start difference. First operand 15 states and 15 transitions. Second operand 15 states. [2018-06-25 12:47:45,628 WARN ]: Spent 141.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 45 [2018-06-25 12:47:46,081 WARN ]: Spent 311.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 43 [2018-06-25 12:47:46,604 WARN ]: Spent 251.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 46 [2018-06-25 12:47:46,605 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:47:46,605 INFO ]: Finished difference Result 17 states and 17 transitions. [2018-06-25 12:47:46,605 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-25 12:47:46,605 INFO ]: Start accepts. Automaton has 15 states. Word has length 14 [2018-06-25 12:47:46,605 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:47:46,606 INFO ]: With dead ends: 17 [2018-06-25 12:47:46,606 INFO ]: Without dead ends: 17 [2018-06-25 12:47:46,606 INFO ]: 0 DeclaredPredicates, 32 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 98 ImplicationChecksByTransitivity, 8.8s TimeCoverageRelationStatistics Valid=181, Invalid=371, Unknown=0, NotChecked=0, Total=552 [2018-06-25 12:47:46,606 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-25 12:47:46,608 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-25 12:47:46,608 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-25 12:47:46,608 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 17 transitions. [2018-06-25 12:47:46,608 INFO ]: Start accepts. Automaton has 17 states and 17 transitions. Word has length 14 [2018-06-25 12:47:46,608 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:47:46,608 INFO ]: Abstraction has 17 states and 17 transitions. [2018-06-25 12:47:46,608 INFO ]: Interpolant automaton has 15 states. [2018-06-25 12:47:46,608 INFO ]: Start isEmpty. Operand 17 states and 17 transitions. [2018-06-25 12:47:46,609 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-25 12:47:46,609 INFO ]: Found error trace [2018-06-25 12:47:46,609 INFO ]: trace histogram [9, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:47:46,609 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:47:46,609 INFO ]: Analyzing trace with hash -1752374252, now seen corresponding path program 8 times [2018-06-25 12:47:46,609 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:47:46,609 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:47:46,610 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:46,610 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:47:46,610 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:47:46,741 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:47,470 INFO ]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:47:47,470 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:47:47,470 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:47:47,476 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 12:47:47,554 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 12:47:47,554 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:47:47,559 INFO ]: Computing forward predicates... [2018-06-25 12:47:48,001 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:47:48,004 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-25 12:47:55,411 INFO ]: Timeout while computing interpolants [2018-06-25 12:47:55,612 WARN ]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:47:55,653 WARN ]: Verification canceled [2018-06-25 12:47:55,657 WARN ]: Timeout [2018-06-25 12:47:55,657 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 12:47:55 BoogieIcfgContainer [2018-06-25 12:47:55,657 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 12:47:55,658 INFO ]: Toolchain (without parser) took 54937.21 ms. Allocated memory was 305.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 258.7 MB in the beginning and 738.6 MB in the end (delta: -479.9 MB). Peak memory consumption was 722.2 MB. Max. memory is 3.6 GB. [2018-06-25 12:47:55,659 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 305.1 MB. Free memory is still 270.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 12:47:55,659 INFO ]: ChcToBoogie took 76.48 ms. Allocated memory is still 305.1 MB. Free memory was 258.7 MB in the beginning and 256.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:47:55,659 INFO ]: Boogie Preprocessor took 36.26 ms. Allocated memory is still 305.1 MB. Free memory was 256.7 MB in the beginning and 255.7 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-25 12:47:55,660 INFO ]: RCFGBuilder took 208.41 ms. Allocated memory is still 305.1 MB. Free memory was 255.7 MB in the beginning and 245.7 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:47:55,662 INFO ]: TraceAbstraction took 54593.65 ms. Allocated memory was 305.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 245.7 MB in the beginning and 738.6 MB in the end (delta: -492.9 MB). Peak memory consumption was 709.3 MB. Max. memory is 3.6 GB. [2018-06-25 12:47:55,667 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 305.1 MB. Free memory is still 270.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 76.48 ms. Allocated memory is still 305.1 MB. Free memory was 258.7 MB in the beginning and 256.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 36.26 ms. Allocated memory is still 305.1 MB. Free memory was 256.7 MB in the beginning and 255.7 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 208.41 ms. Allocated memory is still 305.1 MB. Free memory was 255.7 MB in the beginning and 245.7 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 54593.65 ms. Allocated memory was 305.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 245.7 MB in the beginning and 738.6 MB in the end (delta: -492.9 MB). Peak memory consumption was 709.3 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 17 with TraceHistMax 9, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 18 quantified variables from 8 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 54.5s OverallTime, 9 OverallIterations, 9 TraceHistogramMax, 3.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 56 SDtfs, 20 SDslu, 189 SDs, 0 SdLazy, 72 SolverSat, 51 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 155 GetRequests, 51 SyntacticMatches, 22 SemanticMatches, 82 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 255 ImplicationChecksByTransitivity, 13.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=17occurred in iteration=8, 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, 8 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 40.5s InterpolantComputationTime, 161 NumberOfCodeBlocks, 161 NumberOfCodeBlocksAsserted, 24 NumberOfCheckSat, 146 ConstructedInterpolants, 4 QuantifiedInterpolants, 7465 SizeOfPredicates, 28 NumberOfNonLiveVariables, 1253 ConjunctsInSsa, 265 ConjunctsInUnsatCore, 15 InterpolantComputations, 1 PerfectInterpolantSequences, 0/168 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/bind_expands_vars2.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_12-47-55-678.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/bind_expands_vars2.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_12-47-55-678.csv Completed graceful shutdown