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/ctigar/fig2.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:03:51,663 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:03:51,665 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:03:51,682 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:03:51,682 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:03:51,683 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:03:51,685 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:03:51,686 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:03:51,688 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:03:51,688 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:03:51,689 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:03:51,689 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:03:51,690 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:03:51,691 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:03:51,692 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:03:51,693 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:03:51,694 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:03:51,696 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:03:51,697 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:03:51,698 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:03:51,699 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:03:51,702 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:03:51,702 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:03:51,702 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:03:51,703 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:03:51,704 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:03:51,705 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:03:51,705 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:03:51,706 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:03:51,707 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:03:51,707 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:03:51,708 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:03:51,708 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:03:51,709 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:03:51,710 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:03:51,710 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 15:03:51,723 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:03:51,723 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:03:51,724 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:03:51,724 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:03:51,725 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:03:51,725 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:03:51,725 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:03:51,725 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:03:51,726 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:03:51,726 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:03:51,726 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:03:51,726 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:03:51,726 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:03:51,727 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:03:51,727 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:03:51,727 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:03:51,727 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:03:51,727 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:03:51,728 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:03:51,729 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:03:51,729 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:03:51,781 INFO ]: Repository-Root is: /tmp [2018-06-22 15:03:51,797 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:03:51,804 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:03:51,806 INFO ]: Initializing SmtParser... [2018-06-22 15:03:51,806 INFO ]: SmtParser initialized [2018-06-22 15:03:51,807 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/fig2.c.smt2 [2018-06-22 15:03:51,808 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 15:03:51,898 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/fig2.c.smt2 unknown [2018-06-22 15:03:52,215 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/fig2.c.smt2 [2018-06-22 15:03:52,225 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:03:52,230 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:03:52,230 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:03:52,230 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:03:52,230 INFO ]: ChcToBoogie initialized [2018-06-22 15:03:52,233 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:03:52" (1/1) ... [2018-06-22 15:03:52,279 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:03:52 Unit [2018-06-22 15:03:52,279 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:03:52,280 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:03:52,280 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:03:52,280 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:03:52,300 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:03:52" (1/1) ... [2018-06-22 15:03:52,300 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:03:52" (1/1) ... [2018-06-22 15:03:52,309 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:03:52" (1/1) ... [2018-06-22 15:03:52,309 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:03:52" (1/1) ... [2018-06-22 15:03:52,324 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:03:52" (1/1) ... [2018-06-22 15:03:52,325 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:03:52" (1/1) ... [2018-06-22 15:03:52,327 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:03:52" (1/1) ... [2018-06-22 15:03:52,328 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:03:52,338 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:03:52,338 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:03:52,338 INFO ]: RCFGBuilder initialized [2018-06-22 15:03:52,339 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:03:52" (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) [2018-06-22 15:03:52,354 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:03:52,355 INFO ]: Found specification of procedure False [2018-06-22 15:03:52,355 INFO ]: Found implementation of procedure False [2018-06-22 15:03:52,355 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:03:52,355 INFO ]: Found specification of procedure state [2018-06-22 15:03:52,355 INFO ]: Found implementation of procedure state [2018-06-22 15:03:52,355 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:03:52,355 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:03:52,355 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:03:52,517 INFO ]: Using library mode [2018-06-22 15:03:52,517 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:03:52 BoogieIcfgContainer [2018-06-22 15:03:52,517 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:03:52,522 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:03:52,522 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:03:52,525 INFO ]: TraceAbstraction initialized [2018-06-22 15:03:52,525 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:03:52" (1/3) ... [2018-06-22 15:03:52,526 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5f37ce73 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:03:52, skipping insertion in model container [2018-06-22 15:03:52,526 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:03:52" (2/3) ... [2018-06-22 15:03:52,526 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5f37ce73 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:03:52, skipping insertion in model container [2018-06-22 15:03:52,526 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:03:52" (3/3) ... [2018-06-22 15:03:52,528 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:03:52,537 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:03:52,547 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:03:52,596 INFO ]: Using default assertion order modulation [2018-06-22 15:03:52,597 INFO ]: Interprodecural is true [2018-06-22 15:03:52,597 INFO ]: Hoare is false [2018-06-22 15:03:52,597 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:03:52,597 INFO ]: Backedges is TWOTRACK [2018-06-22 15:03:52,597 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:03:52,597 INFO ]: Difference is false [2018-06-22 15:03:52,597 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:03:52,597 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:03:52,614 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:03:52,627 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:03:52,627 INFO ]: Found error trace [2018-06-22 15:03:52,628 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:03:52,628 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:03:52,635 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 15:03:52,637 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:03:52,638 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:03:52,673 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:03:52,673 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:03:52,673 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:03:52,698 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:03:52,799 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:03:52,803 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:03:52,803 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:03:52,805 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:03:52,822 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:03:52,823 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:03:52,826 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:03:52,961 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:03:52,962 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:03:52,962 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:03:52,963 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:03:52,964 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:03:52,972 INFO ]: With dead ends: 13 [2018-06-22 15:03:52,972 INFO ]: Without dead ends: 13 [2018-06-22 15:03:52,974 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 15:03:52,988 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:03:53,010 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:03:53,011 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:03:53,012 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:03:53,013 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:03:53,013 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:03:53,013 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:03:53,013 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:03:53,013 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:03:53,014 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:03:53,014 INFO ]: Found error trace [2018-06-22 15:03:53,015 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:03:53,015 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:03:53,015 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 15:03:53,015 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:03:53,015 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:03:53,016 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:03:53,016 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:03:53,016 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:03:53,064 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:03:53,343 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:03:53,343 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:03:53,343 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 15:03:53,350 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:03:53,388 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:03:53,395 INFO ]: Computing forward predicates... [2018-06-22 15:03:54,141 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:03:54,175 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:03:54,175 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 15:03:54,175 INFO ]: Interpolant automaton has 9 states [2018-06-22 15:03:54,175 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 15:03:54,176 INFO ]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-22 15:03:54,177 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 15:03:54,776 WARN ]: Spent 263.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 15:03:54,998 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:03:54,998 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:03:54,998 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:03:54,998 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 15:03:54,998 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:03:54,999 INFO ]: With dead ends: 15 [2018-06-22 15:03:54,999 INFO ]: Without dead ends: 15 [2018-06-22 15:03:55,000 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:03:55,000 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:03:55,002 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:03:55,003 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:03:55,003 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:03:55,003 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:03:55,003 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:03:55,003 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:03:55,003 INFO ]: Interpolant automaton has 9 states. [2018-06-22 15:03:55,003 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:03:55,004 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:03:55,004 INFO ]: Found error trace [2018-06-22 15:03:55,004 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:03:55,004 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:03:55,004 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 15:03:55,004 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:03:55,004 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:03:55,005 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:03:55,005 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:03:55,005 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:03:55,102 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:03:55,467 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:03:55,467 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:03:55,467 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 15:03:55,480 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:03:55,527 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:03:55,527 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:03:55,531 INFO ]: Computing forward predicates... [2018-06-22 15:03:56,079 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:03:56,099 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:03:56,099 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:03:56,099 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:03:56,100 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:03:56,100 INFO ]: CoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:03:56,100 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:03:56,400 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:03:56,400 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:03:56,400 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:03:56,400 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:03:56,400 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:03:56,401 INFO ]: With dead ends: 17 [2018-06-22 15:03:56,401 INFO ]: Without dead ends: 17 [2018-06-22 15:03:56,401 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=53, Invalid=157, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:03:56,401 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:03:56,404 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:03:56,404 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:03:56,405 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:03:56,405 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:03:56,405 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:03:56,405 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:03:56,405 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:03:56,405 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:03:56,406 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:03:56,406 INFO ]: Found error trace [2018-06-22 15:03:56,406 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:03:56,406 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:03:56,406 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 15:03:56,406 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:03:56,406 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:03:56,407 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:03:56,407 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:03:56,407 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:03:56,496 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:03:56,792 WARN ]: Spent 105.00 ms on a formula simplification that was a NOOP. DAG size: 25 [2018-06-22 15:03:56,913 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:03:56,913 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:03:56,913 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 15:03:56,930 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 15:03:57,023 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:03:57,023 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:03:57,027 INFO ]: Computing forward predicates... [2018-06-22 15:03:57,301 WARN ]: Spent 166.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 29 [2018-06-22 15:03:57,884 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:03:57,906 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:03:57,906 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2018-06-22 15:03:57,907 INFO ]: Interpolant automaton has 17 states [2018-06-22 15:03:57,907 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 15:03:57,907 INFO ]: CoverageRelationStatistics Valid=47, Invalid=225, Unknown=0, NotChecked=0, Total=272 [2018-06-22 15:03:57,907 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 17 states. [2018-06-22 15:03:58,186 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 32 [2018-06-22 15:03:58,359 WARN ]: Spent 146.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 46 [2018-06-22 15:03:58,680 WARN ]: Spent 287.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 42 [2018-06-22 15:03:58,703 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:03:58,703 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:03:58,704 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:03:58,704 INFO ]: Start accepts. Automaton has 17 states. Word has length 21 [2018-06-22 15:03:58,704 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:03:58,705 INFO ]: With dead ends: 19 [2018-06-22 15:03:58,705 INFO ]: Without dead ends: 19 [2018-06-22 15:03:58,705 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=90, Invalid=330, Unknown=0, NotChecked=0, Total=420 [2018-06-22 15:03:58,705 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:03:58,708 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:03:58,708 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:03:58,708 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:03:58,708 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:03:58,708 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:03:58,708 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:03:58,709 INFO ]: Interpolant automaton has 17 states. [2018-06-22 15:03:58,709 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:03:58,709 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:03:58,709 INFO ]: Found error trace [2018-06-22 15:03:58,709 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:03:58,711 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:03:58,711 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 15:03:58,711 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:03:58,711 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:03:58,712 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:03:58,712 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:03:58,712 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:03:58,771 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:03:59,382 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:03:59,382 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:03:59,382 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) [2018-06-22 15:03:59,397 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:03:59,448 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:03:59,449 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:03:59,453 INFO ]: Computing forward predicates... [2018-06-22 15:04:00,239 WARN ]: Spent 334.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 29 [2018-06-22 15:04:00,879 WARN ]: Spent 387.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 39 [2018-06-22 15:04:01,459 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:04:01,478 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:04:01,478 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 20 [2018-06-22 15:04:01,479 INFO ]: Interpolant automaton has 20 states [2018-06-22 15:04:01,479 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 15:04:01,479 INFO ]: CoverageRelationStatistics Valid=48, Invalid=332, Unknown=0, NotChecked=0, Total=380 [2018-06-22 15:04:01,479 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 20 states. [2018-06-22 15:04:01,829 WARN ]: Spent 308.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 69 [2018-06-22 15:04:02,119 WARN ]: Spent 235.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 35 [2018-06-22 15:04:02,479 WARN ]: Spent 335.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 43 [2018-06-22 15:04:02,961 WARN ]: Spent 440.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 59 [2018-06-22 15:04:03,150 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 38 [2018-06-22 15:04:03,192 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:04:03,192 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:04:03,193 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:04:03,193 INFO ]: Start accepts. Automaton has 20 states. Word has length 25 [2018-06-22 15:04:03,193 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:04:03,194 INFO ]: With dead ends: 21 [2018-06-22 15:04:03,194 INFO ]: Without dead ends: 21 [2018-06-22 15:04:03,194 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=114, Invalid=536, Unknown=0, NotChecked=0, Total=650 [2018-06-22 15:04:03,194 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:04:03,198 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:04:03,198 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:04:03,199 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:04:03,199 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:04:03,199 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:04:03,199 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:04:03,199 INFO ]: Interpolant automaton has 20 states. [2018-06-22 15:04:03,199 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:04:03,200 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:04:03,200 INFO ]: Found error trace [2018-06-22 15:04:03,200 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:04:03,200 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:04:03,200 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 15:04:03,200 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:04:03,200 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:04:03,203 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:04:03,203 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:04:03,203 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:04:03,299 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:04:03,563 WARN ]: Spent 113.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 15:04:04,467 WARN ]: Spent 852.00 ms on a formula simplification that was a NOOP. DAG size: 25 [2018-06-22 15:04:04,674 WARN ]: Spent 140.00 ms on a formula simplification that was a NOOP. DAG size: 33 [2018-06-22 15:04:04,887 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:04:04,887 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:04:04,887 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 15:04:04,900 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:04:04,952 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:04:04,952 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:04:04,957 INFO ]: Computing forward predicates... [2018-06-22 15:04:06,036 WARN ]: Spent 546.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 38 [2018-06-22 15:04:07,869 WARN ]: Spent 1.38 s on a formula simplification. DAG size of input: 55 DAG size of output: 31 [2018-06-22 15:04:08,336 WARN ]: Spent 346.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 39 [2018-06-22 15:04:09,444 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:04:09,463 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:04:09,463 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 23 [2018-06-22 15:04:09,463 INFO ]: Interpolant automaton has 23 states [2018-06-22 15:04:09,463 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 15:04:09,464 INFO ]: CoverageRelationStatistics Valid=64, Invalid=442, Unknown=0, NotChecked=0, Total=506 [2018-06-22 15:04:09,464 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 23 states. [2018-06-22 15:04:10,258 WARN ]: Spent 719.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 97 [2018-06-22 15:04:10,523 WARN ]: Spent 229.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 35 [2018-06-22 15:04:11,202 WARN ]: Spent 647.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 63 [2018-06-22 15:04:11,812 WARN ]: Spent 567.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 69 [2018-06-22 15:04:12,303 WARN ]: Spent 456.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 64 [2018-06-22 15:04:12,994 WARN ]: Spent 532.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 78 [2018-06-22 15:04:13,026 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:04:13,026 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:04:13,027 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:04:13,027 INFO ]: Start accepts. Automaton has 23 states. Word has length 29 [2018-06-22 15:04:13,027 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:04:13,028 INFO ]: With dead ends: 23 [2018-06-22 15:04:13,028 INFO ]: Without dead ends: 23 [2018-06-22 15:04:13,028 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 19 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 8.0s TimeCoverageRelationStatistics Valid=160, Invalid=710, Unknown=0, NotChecked=0, Total=870 [2018-06-22 15:04:13,028 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:04:13,031 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:04:13,031 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:04:13,032 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:04:13,032 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:04:13,032 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:04:13,032 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:04:13,032 INFO ]: Interpolant automaton has 23 states. [2018-06-22 15:04:13,032 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:04:13,033 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:04:13,033 INFO ]: Found error trace [2018-06-22 15:04:13,033 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:04:13,033 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:04:13,033 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-22 15:04:13,033 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:04:13,033 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:04:13,034 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:04:13,034 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:04:13,034 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:04:13,124 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:04:14,014 WARN ]: Spent 576.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 23 [2018-06-22 15:04:14,203 WARN ]: Spent 182.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 42 [2018-06-22 15:04:14,423 WARN ]: Spent 196.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 39 [2018-06-22 15:04:14,573 WARN ]: Spent 138.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 35 [2018-06-22 15:04:15,043 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:04:15,043 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:04:15,043 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:04:15,049 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:04:15,104 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:04:15,104 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:04:15,109 INFO ]: Computing forward predicates... [2018-06-22 15:04:15,781 WARN ]: Spent 605.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 49 [2018-06-22 15:04:16,170 WARN ]: Spent 230.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 31 [2018-06-22 15:04:16,323 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 33 [2018-06-22 15:04:18,080 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:04:18,109 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:04:18,109 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 25 [2018-06-22 15:04:18,109 INFO ]: Interpolant automaton has 25 states [2018-06-22 15:04:18,109 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-22 15:04:18,110 INFO ]: CoverageRelationStatistics Valid=74, Invalid=526, Unknown=0, NotChecked=0, Total=600 [2018-06-22 15:04:18,110 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 25 states. [2018-06-22 15:04:19,165 WARN ]: Spent 955.00 ms on a formula simplification. DAG size of input: 138 DAG size of output: 127 [2018-06-22 15:04:19,449 WARN ]: Spent 238.00 ms on a formula simplification. DAG size of input: 130 DAG size of output: 42 [2018-06-22 15:04:20,026 WARN ]: Spent 540.00 ms on a formula simplification. DAG size of input: 137 DAG size of output: 57 [2018-06-22 15:04:20,531 WARN ]: Spent 468.00 ms on a formula simplification. DAG size of input: 139 DAG size of output: 52 [2018-06-22 15:04:20,929 WARN ]: Spent 353.00 ms on a formula simplification. DAG size of input: 140 DAG size of output: 71 [2018-06-22 15:04:21,623 WARN ]: Spent 637.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 70 [2018-06-22 15:04:22,387 WARN ]: Spent 675.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 97 [2018-06-22 15:04:22,431 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:04:22,431 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:04:22,432 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:04:22,432 INFO ]: Start accepts. Automaton has 25 states. Word has length 33 [2018-06-22 15:04:22,432 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:04:22,433 INFO ]: With dead ends: 25 [2018-06-22 15:04:22,433 INFO ]: Without dead ends: 25 [2018-06-22 15:04:22,434 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 21 SyntacticMatches, 4 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 152 ImplicationChecksByTransitivity, 7.2s TimeCoverageRelationStatistics Valid=192, Invalid=864, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 15:04:22,434 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:04:22,437 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:04:22,437 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:04:22,438 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:04:22,438 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:04:22,438 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:04:22,438 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:04:22,438 INFO ]: Interpolant automaton has 25 states. [2018-06-22 15:04:22,438 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:04:22,439 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:04:22,439 INFO ]: Found error trace [2018-06-22 15:04:22,439 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:04:22,439 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:04:22,440 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-22 15:04:22,440 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:04:22,440 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:04:22,440 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:04:22,440 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:04:22,440 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:04:22,522 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:04:22,773 WARN ]: Spent 128.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 15:04:23,072 WARN ]: Spent 140.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 36 [2018-06-22 15:04:23,246 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 41 [2018-06-22 15:04:23,792 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:04:23,792 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:04:23,792 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:04:23,799 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:04:23,856 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:04:23,863 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 15:04:56,213 WARN ]: Removed 3 from assertion stack [2018-06-22 15:04:56,226 INFO ]: Timeout while computing interpolants [2018-06-22 15:04:56,426 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:04:56,426 WARN ]: Verification canceled [2018-06-22 15:04:56,430 WARN ]: Timeout [2018-06-22 15:04:56,430 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:04:56 BoogieIcfgContainer [2018-06-22 15:04:56,430 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:04:56,431 INFO ]: Toolchain (without parser) took 64205.23 ms. Allocated memory was 308.8 MB in the beginning and 1.1 GB in the end (delta: 794.3 MB). Free memory was 261.3 MB in the beginning and 1.0 GB in the end (delta: -742.7 MB). Peak memory consumption was 827.5 MB. Max. memory is 3.6 GB. [2018-06-22 15:04:56,432 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 273.4 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:04:56,432 INFO ]: ChcToBoogie took 49.13 ms. Allocated memory is still 308.8 MB. Free memory was 259.4 MB in the beginning and 257.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:04:56,432 INFO ]: Boogie Preprocessor took 48.70 ms. Allocated memory is still 308.8 MB. Free memory is still 257.4 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:04:56,433 INFO ]: RCFGBuilder took 179.31 ms. Allocated memory is still 308.8 MB. Free memory was 257.4 MB in the beginning and 247.4 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:04:56,433 INFO ]: TraceAbstraction took 63908.22 ms. Allocated memory was 308.8 MB in the beginning and 1.1 GB in the end (delta: 794.3 MB). Free memory was 247.4 MB in the beginning and 1.0 GB in the end (delta: -756.6 MB). Peak memory consumption was 813.5 MB. Max. memory is 3.6 GB. [2018-06-22 15:04:56,437 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 273.4 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 49.13 ms. Allocated memory is still 308.8 MB. Free memory was 259.4 MB in the beginning and 257.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 48.70 ms. Allocated memory is still 308.8 MB. Free memory is still 257.4 MB. There was no memory consumed. Max. memory is 3.6 GB. * RCFGBuilder took 179.31 ms. Allocated memory is still 308.8 MB. Free memory was 257.4 MB in the beginning and 247.4 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 63908.22 ms. Allocated memory was 308.8 MB in the beginning and 1.1 GB in the end (delta: 794.3 MB). Free memory was 247.4 MB in the beginning and 1.0 GB in the end (delta: -756.6 MB). Peak memory consumption was 813.5 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 38 with TraceHistMax 8, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 14108. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 63.8s OverallTime, 8 OverallIterations, 8 TraceHistogramMax, 11.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 89 SDtfs, 195 SDslu, 516 SDs, 0 SdLazy, 434 SolverSat, 247 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 234 GetRequests, 100 SyntacticMatches, 7 SemanticMatches, 127 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 424 ImplicationChecksByTransitivity, 22.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=25occurred in iteration=7, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 16.9s InterpolantComputationTime, 285 NumberOfCodeBlocks, 285 NumberOfCodeBlocksAsserted, 28 NumberOfCheckSat, 272 ConstructedInterpolants, 0 QuantifiedInterpolants, 833088 SizeOfPredicates, 275 NumberOfNonLiveVariables, 1197 ConjunctsInSsa, 245 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 112/406 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/fig2.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-04-56-447.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/fig2.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-04-56-447.csv Completed graceful shutdown