+1(978)310-4246 credencewriters@gmail.com
  

Description

KITCHEN and BATH

MECHANICAL PLAN

This week you will create a Mechanical plan for both your kitchen and your bath.

This week we will cover the mechanical plan information and specifics for bathrooms.

Watch the YouTube video from the link. This tells shows you the basic form.

There will be a legend covering all the lighting, electrical and mechanical fixtures that you will

use. This legend will show the symbol and a brief description of the fixture.

This may be like “4” inch LED recessed can”, or “2” LED recessed can”. I would need to make a

slight difference in the symbol, as the size in the circle and show both. The legend notes will

have the symbol and what it is for.

Different companies might use slightly different symbols, and that is why the legend appears on

the plan page and drafting package pages. You are telling the reader which symbols you are

using for exactly what.

What You need on the legend-A symbol for each type of lighting. This is:

Recessed cans of different sizes,

Directional cans or spots,

Under cabinet lighting with type or product model and size if different sizes,

Any over counter indirect lighting or LED tape, or under toe kick lighting.

Ceiling fans have a symbol

Decorative chandeliers usually are a large circle with a dot in the center.

Small pendants may be small circles with a dot.

Vents- sometimes the symbol looks like a pinwheel or yen/yang symbol.

Electrical outlets- typical 120/140

Electrical outlets special as range or electric oven which is usually 220 or 240 volts and dryer

which is typically 220 or 240. They are not the typical 120 v outlet.

Switches single, 3way, etc with either no indication by the switch for 1 switch or a 3 for 2

switches. Note the 3 way switch means 2 ways to switch and the circuit. That is a switch symbol

with a 3.

Dimmers are indicated- usually with a little “D” by the switch

GFI switches – with the switch symbol and GFI

Cabel for TV

Note that homes do not have smoke detectors in kitchens and baths because of the natural

amount of smoke and steam that would set them off. You need a smoke detector in the hall by

a bedroom and in the bedroom.

2

Basic information on each fixture or electrical Lighting-

Remember your layers of lighting. -Ambient or general, task for work, decorative lighting can

do other things but its main purpose is decorative, accent, and kinesthetic or movement as

with a candle, a sparkle light catches. There may be different listings, but these include all the

possibilities.

You need several layers to get a rich effect.

Lighting on counters should hit the edge you are working on. This puts a fixture about 30” from

the wall. There is a light over the sink. Lighting should not hit behind your head and cast a

shadow on what you are doing.

You need under-counter lighting for task lighting. It is switched on the wall.

Try and put cans in a basic grid. Keep as orderly as possible.

If a fan has a light, switch it separately. Don’t depend on the fan light for main light.

Note that the number of cans you need for general, overall lighting depends on the size of the

fixture and the actual lamp or bulb you intend to specify. (If your client changes lamps or bulbs

that is, the amount of light or lumens may change.)

In the bath you need lighting In the shower and over the bath typically. You need vanity

lighting. For best lighting, use sconces at the vanity, not a bath bar. Bath bars are cheaper for

the light and installation, but cast shadows down the Face and are not flattering.

Switch your lighting to get the maximum effect. Do not switch the chandelier on the same

circuit as everything else. It is for effect and needs uniqueness. Think about what you might

want on at the same time or by itself.

Switches-Most codes require a light switch at every room entry. This is for safety of course.

Switches must not be within reach of a shower or bath.

Remember you have 4” of wood on either side supporting a door or opening. I cannot put a

switch there.

Switches do not go behind doors. You must be able to open a door ant feel the switch.

Most switches are at a consistent height. This can be noted on the bath and kitchen plans.

If they are at a different height, that then needs to be noted on the plan.

Switches can be in doors and go off when doors close.

Now days, some, as closet switches may be on a timed motion sensor that goes off a time after

last motion.

Closets can have in-door switches or motion sensors.

Dimmers-Put a dimmer on all lighting in the kitchen and Master bath, with maybe a few

exceptions. Guest baths may be without, but it is nice. Maybe not the toilet and shower for

dimmers. It can be a bother to have dimmers in the closet.

Bathrooms really need sconces for the correct lighting, and not bath bars. Bath bars are

cheaper to buy and install for the light.

There are different dimmers for different lights and needs. Lighting technology has and is

changing a lot, so dimmers may change also.

3

Outlets- Note outlet height typical as a plan note. Note any variations on the plan.

You need to look at your appliance’s spec sheets to know where their outlet needs to be. A

range may have a recessed area specifically for the large plug. Ranges and Dryers need high

power usually 220 or 240 v outlets. Some appliances must be on a separate circuit. This is by

code.

The dishwasher may need an outlet or it may be hotwired depending on the code for the area

at that time. The outlet goes within cord length of the dish washer of course. Where is that? I

need to look. It could be under the sink.

The range vent hood needs an outlet, or probably electrical connection. I need to know which

in my area. I also need to note where it should be. The garbage disposal needs a switch of

some type and an outlet. There are several choices now for

The ref. needs an outlet at some predetermined height. Any other electrical appliance needs an

outlet. A TV needs an outlet behind it, and maybe cable.

A toilet washlet or full high-tech toilet that does everything needs an outlet near it.

A spa tub with motor or blower needs a GFI outlet ,(if near water) at a specified location.

GFI outlets-

In kitchens every 2’ approximately along a backsplash. On any area near water, if an island has a

sink. GFI outlets are necessary outdoors. In bathrooms, within 3’ of water. Spa tubs with

motors require GFI outlet under tub.

Codes-Sometimes the code does not require something, but the idea is safety and in new or

major construction the inspector may require more electrical than code requires.

An experienced designer should probably anticipate this. A long glass wall might need a floor

outlet. The contractor would make sure all things get permitted. You would anticipate any

needs and design for those.

Today, companies like Lutron have come up with different switching systems. They cost more

but are cleaner on the wall and easy to use. You can route all circuits to a closet and then use a

simple scene system with buttons to set up lighting combinations and scenes. These then have

a dimmer. You can also do smart switches that can be activated with a voice system like Alexa.

For the Bath-

You need a switch at every entrance, right inside the door so you can reach it easily.

If there is 1 door, and you do not need 2 switches for the circuit, it is a single or plane switch

symbol.

If you have 2 entry doors it is a 3-way switch, a switch symbol with a small 3.

You need decorative lighting as a chandelier if the space is big enough. It is usually switch on its

own circuit.

The sink counter sconces usually have 1 switch unless they are on different areas of the room.

The switches can be at the entry of the bathroom or near the cabinets.

Switches need to be beyond reach of the shower or bath.

You need GFI circuits within 3’ of sinks or water and for a motor for a whirlpool tub.

4

You need an outlet for an electric toilet seat.

For residential design, typically code requires that you need an outlet within 6’ reach of all

areas, or about every 12’.

You will need some ambient or general lighting as cans. These should be bright enough to

illuminate for cleaning.

You need a “wet area” fixture in the shower.

You need an exhaust fan in the bathroom or toilet area. You can have a separate fan to exhaust

steam. The vent fan switch for the toilet area should be within reach of the toilet. It may be

integrated with a light, and in that case needs to be switched separately.

If I have a bathroom door to the exterior, I need a switch to the exterior light.

You can have recessed lighting under a cabinet or in a molding or ceiling detail. That usually is

switched separately.

207.0″
CL
CL
27.5″
15.5″
93.4″
24.0″
15.5″
5.0″
86.1″
25.5″
72.0″
25.5″
24.0″
7.0″
12.0″
1.0″
56.0″
96.0″
96.0″
76.0″
40.0″
55.0″
27.5″
5.0″
25.5″
72.0″
25.5″
93.4″
24.0″
86.1″
CL
CL
207.0″
A
MERNA KHALIL
ELEVATION
INTA 213
BATHROOM ELEVATION
1
2″-01
207.0″
CL
168.9″
55.5″
31.5″
38.1″
9.0″
31.5″
79.5″
12.0″
12.0″
96.0″
96.0″
84.0″
84.0″
55.5″
31.5″
9.0″
31.5″
79.5″
168.9″
38.1″
CL
207.0″
B
MERNA KHALIL
ELEVATION
INTA 213
BATHROOM ELEVATION
1
2″-02
207.0″
CL
38.2″
CL
CL
35.3″
84.0″
49.5″
185.0″
22.0″
56.0″
56.0″
96.0″
96.0″
40.0″
40.0″
185.0″
38.2″
22.0″
35.3″
CL
84.0″
49.5″
CL
CL
207.0″
C
MERNA KHALIL
ELEVATION
INTA 213
BATHROOM ELEVATION
1
2″-03
207.0″
CL
179.5″
24.0″
24.0″
24.0″
24.0″
27.5″
9.5″
35.5″
6.0″ 5.0″
55.0″
12.0″
48.0″
96.0″
96.0″
8.0″
84.0″
40.0″
24.0″
24.0″
24.0″
24.0″
9.5″
35.5″
6.0″ 5.0″
55.0″
179.5″
27.5″
CL
207.0″
D
MERNA KHALIL
ELEVATION
INTA 213
BATHROOM ELEVATION
1
2″-04
Merna Khalil
INTA 213
COST AND QUALITY.
c) Moen Weymouth faucet Model S73104 has a lifetime limited warranty against leaks, drips
and finish defects to the original home owner.
It has a 10 year warranty when used in a multifamily installation and a 5 year limited
warranty when used in a commercial installation.
The Dornbracht faucet is ADA compliant and low lead compliant and therefore not a lifetime
warranty guarantee
.
d)The exterior moving parts of both the Moen Weymouth faucet ans Dornbracht faucet are
both metallic.
e) For the Moen Weymouth faucet the material is always metal constructed duralast and
maybe bronze and coated for Dornbracht it is a low level lead compliant.
f) For dornbracht, the finish type is polished platinum and is applied as a single lever mixer
pull- down with spray function while the moen weymouth finish is nickel which provides a
mirror like warm metallic look.
g)The moen Weymouth operates in stream or spray mode in the pull out or retracted
position while the dornbracht operates in sprayface with an anti-scaling system.
The dornbracht maximum flow is 8L/min at 3 bar flow pressure while the Moen Weymouth
flow is limited to 1.5 gpm(5.7L/min) maximum at 60 psi.
2
a) The American standard cadet achieves low flush through power wash which is a circular
flow of water that helps scrub the bowl clean after each use /flush as it uses 20% less
water than standard toilets while Toto Drake achieves low flush through Tornado flush
whereby surfaces look like new for longer if the water scrubs the bowl as it flushes.
b)The toto drake has the best ratings as it provides a variety of flush mechanisms such as
G-Max, E-max,Cyclone , Tornado and Dual max.
b) A one piece toilet is much more convenient to clean because they lack gaps and corners
in their corners.
c) The American standard cadet provides a selection of toilet types that include one-piece,
two-piece types, wall-hung, WC close coupled and Wc wall-hung toilets with toilety
bowl styles ranging from round-fronted and elongated bowl designs while toto provides
a variety of toilet types which include one –piece, urinals and floor mounted toilets that
include round fronted and elongated bowl designs for extreme functionality
d)
The American standard provides beautifully designed toilets with water efficient capabilities
but toto outshines them with beautifully crafted parts and advanced features.
The American standard provides toilet that come with comfort height which matches ADA
while toto manufactures high end toilets with features like self cleaning, warm hair-drying
and heated seats.
The American standard provides a range of advanced flushing systems that include vormax
flushing system while the toto providesa variety of flushing systems which include G-Max, EMax,Cyclone, Tornado and Dual max.
e) Elongated seat is a longer than round toilets by about 2 inches with a length of 18.5
inches and will technically fit in a round toilet but the fit and comfort is compromised.
f) 2 piece toilet- it is a common type of toilet in U.S where toilet and bowl are separate
pieces and are attached together with bolts and caskets during installation.
3.
SHOWRROMS/SUPPLIERS
a) i,16839 Old U.S,27,Lansing,MI
48906, United States
+1 517-482-0748
ii)4235 Pacific St, Rocklin, CA
95677, United States
+1 916-304-4489
b) i) mc daniels kitchen and bath showroom
ii) In-store shopping Kitchen and Bath Showroom
4)
The Autocad modifications are submitted along .
Information and Computation 204 (2006) 1325–1345
www.elsevier.com/locate/ic
Table design in dynamic programming
Peter Steffen * , Robert Giegerich
Faculty of Technology, Bielefeld University, Postfach 10 01 31, 33501 Bielefeld, Germany
Received 9 August 2004; revised 17 January 2006
Available online 8 August 2006
Abstract
Dynamic Programming solves combinatorial optimization problems by recursive decomposition and tabulation of intermediate results. The first step in the design of a dynamic programming algorithm is to decide
on the set of tables that will hold optimal solutions to subproblems. This step predetermines the shape of the
dynamic programming recurrences as well as the asymptotic efficiency of the algorithm in time and space. We
study dynamic programming in a formal framework where design of tables and problem decomposition can
be done independently. Our main result shows that choosing a good table design for a given decomposition is
an NP-complete problem. A heuristic or approximate approach is therefore needed to automate good table
design. We report on a strategy that combines user annotation and a brute force algorithm, which is shown
to perform well in a large application.
© 2006 Elsevier Inc. All rights reserved.
Keywords: Dynamic programming; Programming methodology; NP completeness; Space-time trade-off
1. Introduction
1.1. Motivation
Dynamic Programming is an elementary and widely used programming technique. Its roots reach
back half a century, when the method and its applications were explored in the work of Bellman
∗
Corresponding author. Fax: +49 521 106 6411.
E-mail addresses: psteffen@techfak.uni-bielefeld.de (P. Steffen), robert@techfak.uni-bielefeld.de (R. Giegerich).
0890-5401/$ – see front matter © 2006 Elsevier Inc. All rights reserved.
doi:10.1016/j.ic.2006.02.006
1326
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
and others [4,5]. Today, introductory textbooks on algorithms usually contain a section devoted
to dynamic programming [2,8,9,14,20,26], where simple problems like matrix chain multiplication,
longest common subsequence, polygon triangulation, string comparison, neatly printing of paragraphs, planning a company party, or construction of optimal binary search trees are commonly
used for the exposition. This programming technique is mainly taught by example. Once designed,
all dynamic programming algorithms look kind of similar: they are cast in terms of recurrences
between table entries that store solutions to intermediate problems, from which the overall solution is constructed in a more or less sophisticated case analysis. The first design step is normally a
decision about the tables that are required. Their choice is not difficult with problems that require
a single or a very small number of tables. However, this simplicity is quickly lost when turning to
more sophisticated problems.
In biological sequence analysis, our specific field of application, dynamic programming algorithms are used on a great variety of problems, such as protein homology search, gene structure
prediction, motif search, analysis of repetitive genomic elements, RNA secondary structure prediction, or interpretation of data from mass spectrometry [14,11,3]. The higher sophistication of these
problems is reflected in a large number of recurrences—sometimes filling several pages—using more
complicated case distinctions, numerous tables and elaborate scoring schemes. Computational efficiency is important, both in time and space, as genomic data tend to be very large.
As a consequence, among experts in the field the design of successful dynamic programming recurrences used to be considered a matter of experience, talent, and luck. Design as well as programming errors are detected long after programs go into production use, and occasionally it takes an
exceptionally long time until a simple (in hindsight!) but important improvement is discovered.
An algebraic style of dynamic programming (ADP) has recently been advocated [12,13], designed
to make dynamic programming algorithm development for biosequence analysis more productive
and the resulting implementations more reliable. Although originally developed for biosequence
analysis, the ADP approach pertains to all dynamic programming problems that have sequential
input and whose subproblems are related to contiguous subsequences of the input. This includes
all the examples, both from text books and biosequence analysis, mentioned above. ADP allows us
to formulate dynamic programming algorithms on a more convenient level of abstraction, based
on algebras and tree grammars. It cleanly separates (conceptually) the traversal of the search space
from the actual evaluation of solutions, and it also separates (conceptually) efficiency concerns
from the logic of the algorithm.
In the ADP approach the problem decomposition is defined using a tree grammar. Therefore,
the design of a dynamic programming algorithm can be done independent of a particular choice of
tables. Some (but not all) of the nonterminal symbols in the grammar must eventually be mapped to
dynamic programming tables—their choice is what we call the table design problem. A particular
choice is called a table configuration. Given the grammar and the table configuration, we can automatically generate dynamic programming recurrences. Thus, the dynamic programmer is liberated
from error-prone subscript fiddling. This is the state of development reported in [13].
Here, we study the problem of automating not only the derivation of recurrences, but also table design. A good table configuration is crucial for efficiency—it makes the difference between exponential
and polynomial runtime of alternative implementations of the same algorithm, and, if the runtime is
polynomial, the table configuration determines the polynomial degree and the space requirements.
A configuration that minimizes both in a precise sense defined later (Definition 10) is called optimal.
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
1327
1.2. Main results
Finding good and optimal table configurations is the problem studied in this article. Previously,
this has been the programmer’s responsibility—explicitly so when using the ADP approach, or
implicitly otherwise. A most ambitious goal would be to completely automate this step, virtually
freeing the program designer from efficiency concerns. However, our main result here shows that a
complete automation of table design is computationally infeasible: both the choice of a good table
configuration and the choice of an optimal configuration are NP-complete problems. Consequently, we develop a pragmatic approach that tries to reduce the problem size by various means to the
point where the problem can be solved to optimality.
1.3. Related work
Dynamic programming problems as addressed within the ADP framework can be seen as a special case of the extensively studied algebraic path problems. See [24] for a review, and the recent
book by Pachter and Sturmfels [22], which summarizes applications of the algebraic view to problems in bioinformatics. Algebraic path problems are optimization problems over graphs defined
via a semiring structure (S, ⊕, ), where S is the domain of scores, ⊕ the objective function (such
as minimization) applied when joining paths, and is the function that combines scores when
extending paths. ADP is somewhat richer semantically, as every function in an evaluation algebra
is a separate instance of the operation, which must satisfy the semiring axioms, and may operate on several arcs simultaneously. As a consequence, the optimal “path” is actually a tree. In the
graph problem framework, the underlying graph structure is usually given explicitly as input. In the
ADP approach, the input is always a sequence, and the graph structure remains implicit. For each
problem instance, data dependencies (paths) are determined according to the tree grammar. Many
mathematical observations from graph problems carry over to the ADP approach, which can be
seen as extending algebraic graph problems towards easier programming in specialized, but also
more sophisticated application domains. In the context of algebraic path problems, dynamic programming is one of many possible solution strategies, and the problem of minimizing the number
of dynamic programming tables, our topic here, is not explicitly addressed.
The approach to represent dynamic programming problems as graphs is also followed by Bodlaender and Telle [6]. They examine to systematically derive space-efficient variants of dynamic
programming algorithms that not only calculate an optimal value, but also calculate the corresponding candidates. They demonstrate the method on two dynamic programming problems on
graphs and give some ideas for generalization. The problems studied there are all based on a single
recurrence with only a single table type. It is not clear whether these techniques can be applied to
more general dynamic programming problems as addressed within the ADP framework.
Memory requirements in dynamic programming is a recurring theme in the literature. One common general technique is the reuse of memory for entries that are no longer needed during a calculation [14]. Applying this technique is often easy in dynamic programming problems where only the
optimal result is to be computed, but becomes difficult, when also the candidates responsible for the
optimal solutions need to be constructed in a backtrace phase [6]. Several improvements exist for
available dynamic programming algorithms, most notably the sequence alignment problem [15,21],
which can be improved from O(n2 ) to O(n) space requirements. Most often, these improvements
1328
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
rely on deeper knowledge about the problem domain, and can not be applied to general dynamic
programming problems.
Some related work is also done in the program transformation community. In [19], Liu and Stoller
describe a method to automatically transform recursive programs into dynamic programming programs that achieve optimal time and space requirements. The method is based on a static analysis
of the data dependencies, which allows to store only those solutions to subproblems that would
otherwise be calculated more than once. Their technique is capable of generating space efficient
versions of many standard dynamic programming problems. Our method is different in the sense
that we allow to recalculate subproblems in order to save space, as long the overall runtime of the
algorithm stays asymptotically optimal.
1.4. Basic terminology
Alphabets. An alphabet A is a finite set of symbols. Sequences of symbols
are called strings.

1
n+1
n
+
ε denotes the empty string, A = A, A
= {ax|a ∈ A, x ∈ A }, A = n 1 An , A∗ = A+ ∪ {ε}.
|a1 · · ·an | = n for n 0.
Signatures and algebras. A signature over some alphabet A consists of a sort symbol S together
with a family of operators. Each operator o has a fixed arity o : s1 · · ·sko → S, where each si is either
S or A. A -algebra I over A, also called an interpretation, is a set SI of values together with a
function oI for each operator o. Each oI has type oI : (s1 )I · · ·(sko )I → SI where AI = A.
A term algebra T arises by interpreting the operators in as constructors, building bigger terms
from smaller ones. When variables from a set V can take the place of arguments to constructors,
we speak of a term algebra with variables, T (V), with V ⊂ T (V). By convention, operator names
are capitalized in the term algebra.
Trees and tree patterns. Terms will be viewed as rooted, ordered, node-labeled trees in the obvious
way. All inner nodes carry (non-nullary) operators from , while leaf nodes carry nullary operators
from or symbols from A. A term/tree with variables is called a tree pattern. A tree containing a
designated occurrence of a subtree t is denoted C[. . .t. . .].
A tree language over is a subset of T . Tree languages are described by tree grammars, which
can be defined in analogy to the Chomsky hierarchy of string grammars. In tree grammars, nonterminal symbols and variables coincide. Here, we use regular tree grammars, originally studied in
[7]. Our further specialization lies solely in the distinguished role of A.
Definition 1 (Tree grammar over and A).
A regular tree grammar G = (V , Z, P) over and A is given by
• a set V of nonterminal symbols,
• a designated nonterminal symbol Z, called the axiom, and
• a set P of productions of the form v → t, where v ∈ V and t ∈ T (V). v → t1 | · · · |tn shall denote
the short form for v → t1 , . . . , v → tn .
The derivation relation for tree grammars is ⇒∗ , with C[. . .v. . .] ⇒ C[. . .t. . .] if v → t ∈ P . The
language of v ∈ V is L(v) = {t ∈ T |v ⇒∗ t}, the language of G is L(G ) = L(Z).
For convenience, we add a lexical level to the grammar concept, allowing strings from A∗ in
place of single symbols. L = {char, string, empty} is the set of lexical symbols. By convention,
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
1329
Fig. 1. Top: Example yield grammar and two evaluation algebras. The axiom symbol is pal, and char denotes
an arbitrary character. Middle: The corresponding recurrences specialized for algebra dist. For lack of space, the
initialization equations are omitted. Bottom: Four candidate structures in the search space for the best approximate
separated palindrome structure for the string “sassafras”. Under algebra dist the candidates evaluate to scores (from
left to right) 7, 5, 4 and 3.
1330
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
L(char) = A, L(string) = A∗ , and L(empty) = {ε}. At this point, the reader may want to glance
ahead at the tree grammar shown in Fig. 1, upper left.
The yield function y on the trees in T is defined by y(a) = a for a ∈ A, and y(f(x1 , . . . , xn )) =
y(x1 ) · · · y(xn ), for f ∈ and n 0. Note that nullary constructors by definition have yield ε, hence
the y(t) is the string of leaf symbols from A in their left to right order in t. The yield size of v ∈ V is
sup{|y(t)| | v ⇒∗ t}. For the lexical symbols, we obtain the yield sizes 0 for empty, 1 for char, and ∞
for string.
1.5. Running example: palindromic structures in strings
As a running example, we shall use the analysis of palindromic structures in strings. A separated
palindrome [14] is a string of the form uv(u−1 ). In “abcdeba”, for example, the separator v could be
chosen to be “cde”, “bcdeb”, or “abcdeba”. Intuitively, we might say that the first choice is the best,
as it maximizes the length of u. Generally, we have some scoring scheme that determines which palindromic structure is best for a given string. In approximate separate palindromes we allow differences
between u and u−1 , using the familiar string edit model with replacements, deletions and insertions.
With such generalization, the number of alternative palindromic structures for a given string becomes very large. Using different scoring schemes, we may formulate the optimization objectives
of maximizing self-similarity, or minimizing differences, with slightly different applications.
The choice of this example is motivated by the following properties:
• It uses familiar string editing terminology and does not require much background explanation.
• It has relevant applications, as the secondary structures formed by RNA molecules are isomorphic to approximate separated palindromes which, as a further generalization, can also be nested
recursively.
• It has about the minimal size required to demonstrate the effects of different table designs.
• It is small enough to easily verify the recurrences that are generated from the more abstract
description.
The last aspect may be seen as the drawback of the example not being sophisticated enough: It
can be solved easily by ad hoc means, and does not motivate the use of a formal method and the
desire to automate table design. This aspect is addressed in Section 3.5, where we report on a “real
life” application.
2. The algebraic approach to dynamic programming
In order to study the table design problem in general, i.e., independent of a particular dynamic
programming algorithm, 1 we need a framework that (1) comprises a clearly defined and practically
significant class of dynamic programming problems, (2) separates the issue of tabulation from the
1 We study the computational complexity of table design, an activity heretofore performed by human programmers.
This must not be confused with studying the complexity of a particular application problem, which may be solved by
dynamic programming, but also by other means.
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
1331
issue of problem decomposition, and hence, (3) allows us to reason about different implementations
of the same dynamic programming algorithm for any problem in this class.
Therefore, we direct our attention to dynamic programming problems and algorithms that can
be expressed in the formal framework of algebraic dynamic programming (ADP), which achieves
(1–3). In the following we give a brief introduction into ADP recapitulated from [13]. In the conclusion section, we shall discuss the extent to which our results pertain to dynamic programming in
general.
2.1. Core concepts of algebraic dynamic programming
Dynamic programming is a programming paradigm which offers much variation. One might
informally circumscribe it as solving combinatorial optimization problems by recursive decomposition and tabulation of intermediate results. But not only optimization, but also counting and
enumeration problems can be solved in this way. The problem decomposition is often guided by
parsing the input in multiple ways; however, someone might also consider algorithms like Dijkstra’s shortest path and its generalizations [10,17] as dynamic programming algorithms, where the
tabulation is related to the output rather than the input.
The ADP approach comprises a well-defined class of dynamic programming problems, which,
as stated before informally, can be described by grammars and algebras. The grammar defines the
search space for all possible inputs, the algebra the scoring of arbitrary solution candidates. A
problem instance is given by a particular input sequence. We shall now formally introduce these
concepts.
Definition 2. Let A be an alphabet and be a signature, w ∈ A∗ and t ∈ T . t is called a potential
candidate for w if y(t) = w.
A candidate represents a certain internal structure associated with w. We use the term potential candidate here, because further conditions will be imposed on candidates soon. Fig. 1, bottom shows
four alternative candidates for the same input.
Definition 3 (Evaluation algebra). Let be a signature with sort symbol Ans. A -evaluation
algebra I is a -algebra augmented with an objective function hI : P (AnsI ) → P (AnsI ), where
P (AnsI ) denotes the power set of AnsI . The score of candidate t ∈ T achieved under -evaluation algebra I is tI . If there are several alternative candidates, say {t1 , …, tk }, then hI ({t1 , …, tk })
denotes our choice.
It remains to define precisely the search space for a given input w. Usually, the candidate set is
much smaller than the potential candidates {t ∈ T |y(t) = w}. We need a formalism to describe the
candidate set.
Definition 4 (Yield grammars and yield languages). Let G be a tree grammar over and A, and y
the yield function. The pair (G , y) is called a yield grammar. It defines the yield language L(G , y) =
{y(t)|t ∈ L(G )}.
Deriving a string in a yield grammar can be seen as a two stage process: first a tree in L(G )
is generated, and then all the tree structure is erased. Recovering it is the task of search space
construction.
1332
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
Definition 5 (Yield parsing). Given a yield grammar (G , y) over A and a sequence w = w1 · · · wn ∈ A∗ ,
the yield parsing problem is to find PG (w) = {t ∈ L(G )|y(t) = w}. A potential candidate t is a proper
candidate if t ∈ L(G ).
Proper candidates will just be called candidates in the sequel. Note that the input string w must
be “parsed” into trees t ∈ L(G ) ⊆ T , each of which in turn has a derivation according to the tree
grammar G . These derivations must exist—they ensure that candidate t corresponds to a proper
problem decomposition—but otherwise, they are irrelevant and will play no part in the sequel.
Yield parsing takes a string as its input, and therefore, although based on a tree grammar, it is
more closely related to string parsing than to tree parsing methods. Its closest relatives are methods
for parsing ambiguous context free languages, such as Earley’s or the CYK algorithm [1]. While
CYK is actually a dynamic programming algorithm and can parse any context free language in
O(n3 ) time, this efficiency result does not carry over to yield parsing. CYK requires a grammar
transformation; its analog for tree grammars is prevented by . This is known as the yield parsing
paradox and is discussed in detail in [13].
For the present development, we assume the availability of a correct yield parser PG , given as a
family of parser functions. We denote by pq the yield parser function for the nonterminal or lexical
symbol q, and with pq (i, j) the application of pq on the input subword wi+1 · · · wj . It returns the set
of all t ∈ L(q) such that y(t) = wi+1 · · · wj .
Given that yield parsing constructs the search space, all that is left to do is to evaluate the
candidates in a given algebra rather than simply returning the trees.
Definition 6 (Algebraic dynamic programming).
• An ADP problem is specified by a signature over A, a yield grammar (G , y) over , and a
-evaluation algebra I with objective function hI .
• An ADP problem instance is posed by a string w ∈ A∗ . The search space it spawns is the set of
all its parses, PG (w).
• Solving an ADP problem is computing hI {tI | t ∈ PG (w)} in polynomial time and space with
respect to |w|.
Taking the above definition naively and computing all candidates before evaluating them would
hardly allow us to achieve polynomial efficiency. The number of parses for w ∈ A∗ can be exponential in |w|. An example is the tree grammar
where a yield string an b has 2n parses. In such a case, the size of the answer dominates the computational cost both in terms of time and space. In the subsequent analysis, we assume that eventually,
only a single, optimal answer is to be reported. Hence, the number of solutions may be reduced
by applying the objective function already to alternative intermediate results from subproblems.
But even so, there is the possibility that the (single) result for a subproblem is calculated many
times, resulting in exponential runtime. The remedy to this source of inefficiency is tabulation of
intermediate results, and re-use rather than re-calculation.
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
1333
These two considerations are well-known as Bellman’s Principle of Optimality. In the algebraic
framework, it reads as follows:
Definition 7 (Algebraic version of Bellman’s Principle). An evaluation algebra I satisfies Bellman’s
Principle, if for each k-ary operator f in and all answer sets z1 , . . . , zk , the objective function hI
satisfies
hI ( { fI (x1 , . . . , xk ) | x1 ∈ z1 , . . . , xk ∈ zk } )
= hI ( { fI (x1 , . . . , xk ) | x1 ∈ hI (z1 ), . . . , xk ∈ hI (zk ) } )
as well as
hI ( z ∪ z ) = hI ( hI (z) ∪ hI (z ) ).
The practical consequence of the optimality principle is that we may push the application of the
objective function inside the computation of subproblems. The parsers pq may apply the choice
function to their alternative results, and store the outcome for later use. Thus we may prevent combinatorial explosion without affecting the overall result. The question, now, is which intermediate
results need tabulation. This is a classical space-time trade-off; using more tables we can make the
program run faster. How to exploit this trade-off in an optimal way is the subject of our current
investigation.
Fig. 1 collects our formulation of the approximate separated palindrome example in the ADP
framework. It shows (top left) the yield grammar defining approximate, separated palindromic
structures. Recall that any string can be parsed as such a palindrome in many ways, with the evaluation algebra determining the best palindromic structure. Four candidates for the string “sassafras”
are shown in the bottom part of the Figure. Two evaluation algebras are given (top right), algebra
sim maximizing self-similarity, and algebra dist minimizing differences. The middle part of Fig. 1
shows the explicit recurrences derived from the grammar and algebra dist.
2.2. Algebraic dynamic programming in practice
The preceding section is a condensed summary of main concepts underlying the algebraic approach to dynamic programming, only to the extent they are required for our present study. ADP
has been implemented as an embedded domain specific language, and is used for (but not restricted
to) the development of biosequence analysis algorithms. This language offers various additional
features useful in practice, like a convenient syntax for writing grammars, a more elaborate lexical
level, many-sorted signatures with a choice function for each sort, syntactic predicates associated
with productions, and more. The reader is referred to [13], where the ADP approach is presented
in full detail, and the literature cited therein. This article also contains a section devoted to the
frequently asked question why context free grammars are just not quite adequate to capture the
essence of dynamic programming over sequence data, and yield grammars must be used instead.
In previous programming practice, table design was a responsibility of the programmer. The
desire to automate it arises from two sources: (1) As ADP cuts down program development efforts, we embark on more sophisticated problems and the grammars get larger. We report on one
such case in Section 3.5. It is no longer easy to show that one has found an optimal table design.
1334
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
(2) In a recently started project on RNA secondary structure analysis, specialized grammars that
model families of structures with a common shape will be generated from the data. This is done
in an iterative way which does not permit human intervention, such that a good automated table
design is essential.
3. Tabulation and efficiency analysis
When all nonterminal symbols are tabulated, the runtime efficiency of the tabulating yield parser
is known. It depends on the width of the grammar:
Definition 8 (Width of productions and grammar). Let t be a tree pattern, and let k be the number of nonterminal or lexical symbols in t whose yield size is not bounded from above. We define
width(t) = k − 1. Let Pv = {t|v → t ∈ P }. We define width(v) = maxt∈Pv {width(t)} and width(G ) =
maxv∈V {width(v)}.
In this case, the execution time is O(n2+width(G ) ) [13]. This implies minimal runtime, but maximal
space consumption, and is what we want to improve upon by a more clever table design.
In Fig. 1, middle part, we show the recurrences that implement the tabulating yield parser
for the example grammar. (We do not discuss here how these recurrences are derived from
the grammar.) Efficiency analysis in this case is simple. With all intermediate results stored in
the five tables match, . . . , inner, the runtime is solely determined by the outer for-loops which
leads to an execution time of O(n2 ). In case of productions with width(v) 1, for example
v → N(string, v), the recurrence equations and the eventual implementation of the corresponding
parsers would contain additional loops for moving subword boundaries resulting in optimal
runtimes of O(n3 ) or more. While tabulating everything yields optimal efficiency in terms of
execution time, it may require more space than really needed. Conversely, the yield parser
may implement a parser for each nonterminal symbol as a recursive function—resulting in low
space requirements for tables (none, to be precise), but exorbitant inefficiency, and most likely
a runtime stack overflow. The solution is to assign a table configuration to the grammar that
achieves an optimal balance.
3.1. Efficiency analysis for a given table configuration
In order to make more precise statements about the usage of tables and recursive functions, we
define:
Definition 9 (Table configuration). Let G = (V , Z, P) be a tree grammar over and PG the corresponding yield parser. A table configuration ϑ is a subset ϑ ⊆ V denoting that for all q ∈ ϑ the parser pq is
to be tabulated and for all q ∈ ϑ the parser pq is to be implemented as a recursive function. PGϑ shall
represent the yield parser PG for yield grammar (G , y) under table configuration ϑ. P (V) denotes the
set of all possible table configurations.
Note that the semantics of the tabulating yield parsers PGϑ are equivalent for all ϑ ∈ P (V). We
will distinguish between good and optimal table configurations.
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
1335
Definition 10 (Good and optimal table configurations). A configuration is good if it uses the minimal
number of tables that leads to polynomial runtime. A configuration is optimal if it uses the minimal
number of tables that leads to a runtime with the best possible polynomial degree.
Note that our notion of optimality includes a space-time trade-off. A grammar with a good table
configuration may still contain a subgrammar whose dependencies raise runtime complexity to an
arbitrary (but fixed) polynomial degree. Extra tables can be assigned to reduce this degree—hence
an optimal configuration, in general, holds more tables than a good one. For example, the second
configuration shown in Fig. 2 is good (using 1 table), while the first configuration is optimal (using
3 tables).
Definition 11 (Dependence mapping). Let S = V ∪ L be the set of nonterminal and lexical symbols
in G . The dependence mapping u for q ∈ V and input length n is given by u(q, n) = (d1 , . . . , dr ) where
each dk , 1 k r represents a dependence property dk ∈ S × IN such that dk = (qk , iqk + jqk ) if
and only if the parser pq (0, n) uses the result of pqk (iqk , n − jqk ). For convenience, we simply denote
(qk , sqk ) ∈ u(q, n).
Theorem 1. The runtime of an ADP algorithm implemented by a tabulating yield parser PGÏ‘ on input
w of length n is given by r(PGÏ‘ , n) where:
r̄(ϑ, q, 0) = 1
(1)
Fig. 2. Three dependence graphs for the yield grammar of Example 1.5, with corresponding table configurations ϑ
and circuit degrees (G). The vertices are numbered as follows: 1 → pal, 2 → del, 3 → ins, 4 → match, 5 → inner.
Table access dependences are drawn as dotted edges. The runtime of the yield parser PG under table configuration ϑ is
denoted by r(PGÏ‘ , n).
1336
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345

1
1
r̄(ϑ, q, n) =

(q ,sq )∈u(q,n) r̄(ϑ, q , n − sq )
2
n · r̄(ϑ, q, n) for q ∈ ϑ
r(Ï‘, q, n) =
r̄(ϑ, q, n)
otherwise

r(PGÏ‘ , n) = O(max r(Ï‘, q, n))
q∈V
for q ∈ L
for q ∈ V , q ∈ ϑ
otherwise
(2)
(3)
(4)
Proof. The dependence mapping u(q, n) provides all calls to lexical or nonterminal parsers in the
calculation of parser pq on input length n. Without loss of generality we assume that each parser terminates at an input of length 0 (1). Lexical parsers and table accesses (2) can be performed
in constant time. In case of a non-tabulated parser pq (2), the parser pq is called with an input
length reduced by sq . The outer for-loops for a tabulated parser lead to a minimal effort of at least
O(n2 ) (3) and the overall runtime of the algorithm (4) is determined by the parser with the maximal
asymptotic runtime.
This of course gives sparse information about a closed form for r(PGÏ‘ , n). All we know is that if
all productions are tabulated, the runtime is solely affected by the constants in (2) and the outer
for-loops of (3).
In case of non-tabulated productions, (2) is defined recursively, which makes reasoning about
complexity more difficult. Tabulating no production at all will in most cases lead to an exponential
runtime. In the following we will investigate how to find the minimal numbers of tables needed to
achieve a polynomially bounded runtime r(PGÏ‘ , n).
3.2. Staying polynomial
The number of dependences for a parser pq is bounded by |u(q, n)| = O(nwidth(q) ). Therefore,
r(PGÏ‘ , n) can only become exponential in the presence of recursive calls between parser functions
(Eq. 2).
For the following developments it is convenient to introduce some terminology for graphs: A
directed graph G = (V , E) is given by a nonempty set V = {v1 , . . . , vs } of vertices and a set E =
{e1 , . . . , em } of edges consisting of ordered pairs of elements of V . A directed graph with multiple
edges is called a directed multigraph with edges given as a multiset E. A loop is an edge connecting a
vertex with itself. In the following we only consider directed multigraphs with loops allowed which
we will simply call graphs. In a weighted graph each edge ei is also associated with a weight w(ei ).
A directed walk is a sequence = v0 e1 v1 e2 · · · el vl , where vi ∈ V , ej ∈ E for 0 i l, 1 j l,
and each edge ej is directed out of vertex vj−1 and directed into vertex vj . Note that the edges and
vertices in are not necessarily distinct. The length of a walk is the number of edges in the sequence
and is denoted
by l( ). The weight of a walk is the sum of the weights of its edges and is denoted
l( )
by w̃( ) = i=1 w(ei ).
A circuit is a closed walk with v0 = vl and all edges distinct. Under this definition a loop is also
a circuit. Two circuits are distinct if one is not a cyclic permutation of the other. The circuit degree
(v) of a vertex v shall be the number of distinct circuits containing v. We define the circuit degree of
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
1337
a graph G as (G) = maxv∈V (v). A circuit which contains no vertex more than once (apart from
the initial one), is called elementary.
The dependence mapping given by u for a yield parser PGÏ‘ can be represented by a weighted
directed dependence graph G with the nonterminal set V as vertex set and an edge from q to qk with
weight sqk for each (qk , sqk ) ∈ u(q, n). Such a graph represents all dependences, regardless whether
by table access or by function call. A graph limited to function call dependences can be derived by
restricting the edge set to edges directed into vertices from V Ï‘.
In the following we restrict the analysis to grammars G with width(G ) = 0. This leads to parsers
with constant dependence, i.e. all references to parser functions have the form pq (i + iq , j − jq ), with
iq , jq ∈ IN and iq , jq 0. This restriction is necessary in order to obtain graphs that are independent
from the input length n contained in the dependence mapping u.
Definition 12 (Dependence graph). Let PGϑ be a yield parser for yield grammar (G , y) under table configuration ϑ and let u be the corresponding dependence mapping. The dependence graph G(PGϑ ) is
given by the grammar’s nonterminal set V as vertex set and edges E = {e1 , . . . , em }. Edge ei = (q, qk )
with w(ei ) = sqk is in E if and only if qk ∈ ϑ and (qk , sqk ) ∈ u(q, n). For convenience, we denote G
for G(PGÏ‘ ).
The use of the dependence graph is influenced by [16] where such graphs are used to represent systems of uniform recurrence equations. Fig. 2 shows three graphs with different table configurations
and circuit degrees (G) for the palindrome example.
Each edge in the dependence graph represents a function call between two parser functions. A
walk in the graph can therefore be interpreted as a sequence of consecutive function calls where
the weight w̃( ) of the walk is the length of the “consumed” input and the length l( ) is the number
of required function calls.
This leads to the following relation between the runtime of a yield parser and its dependence
graph:
Theorem 2. Let PGÏ‘ be a tabulating yield parser with corresponding dependence graph G. Then, PGÏ‘ has
polynomial runtime if and only if (G) 1.
Proof. If there is no vertex on at least two different circuits, each recursive function is called at most
once for each combination of parameters, such that the runtime is polynomial. If there is such a
vertex v, a call on v can trigger two recursive calls to v. Since the recursion depth is linear, this leads
to O(2n ) calls, and the runtime is exponential.
3.3. NP-completeness of table design
Theorem 2 gives a convenient property to distinguish between polynomial and exponential runtimes of a tabulating yield parser. In order to find good table configurations, we need to search
for configurations that lead to dependence graphs with (G) 1 while using a minimal number of
tables.
A simple algorithm is to systematically test all possible table configurations for their impact on
the number of circuits in the dependence graph. Such approach would be exponential in the number
of nonterminal symbols, so the question arises whether a better algorithm exists.
1338
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
Graph theory is a stomping ground for NP-complete and harder problems and provides a rich
theory on these kinds of questions. And indeed, we can utilize a powerful result from graph theory
to give an answer to the question stated above:
Theorem 3. (NP-completeness of good table design) Finding the minimal number of tables to prevent exponential runtime of an ADP algorithm implemented by a tabulating yield parser PG is
NP-complete.
Proof. Recall the construction of the dependence graph in Definition 12. The edge set E for the minimal table configuration ϑ = ∅ represents all dependences between parsers for the situation that no
results are tabulated. Adding a table for the parser pq to the configuration results in deletion of all
edges directed into the corresponding vertex q. Obviously, for the number of circuits in the graph
this has the same effect as deleting the vertex q itself. This leads to the observation that finding
the minimal number of tables to prevent exponential runtime is equivalent to finding the minimal
number of vertices which must be deleted from the dependence graph such that the resulting graph
contains no vertex which is part of two or more circuits. And this is exactly a classic node-deletion
problem:
For a fixed graph property , find the minimum number of nodes (or vertices) which must be
deleted from a given graph so that the result satisfies [18].
It was shown in [18] that if is a “nontrivial” property which is “hereditary” on induced subgraphs, then the node-deletion problem for is NP-hard. Furthermore, if testing for can be
performed in polynomial time, then the node-deletion problem for is NP-complete.
In our application, the property is: the graph contains no vertex which is part of two or more
circuits. To finish the proof, we show that satisfies the properties claimed above. A graph property
is nontrivial if infinitely many graphs satisfy it and infinitely many graphs fail to satisfy it. This is
clearly given for . A property is hereditary if for a given graph satisfying , every node-induced
subgraph also satisfies . It is obvious that all subgraphs of a graph containing no vertex being
part of two or more circuits retain this property. Finally, can be tested for in polynomial time. A
simple algorithm is to calculate all strongly connected components of the graph—which is linear in
the number of vertices and edges [27]—and to check whether each of them is either a single vertex
or an elementary circuit—which is linear as well. Hence, finding the minimal number of tables to
prevent exponential runtime is NP-complete.
Of course, in practical applications we are mostly interested in the optimal configurations, not
necessarily in the good ones. We can use the same approach to show the NP-completeness of the
problem of finding optimal configurations.
Theorem 4 (NP-completeness of optimal table design). Finding the minimal number of tables that are
necessary to achieve the best possible asymptotic runtime of an ADP algorithm implemented by a
tabulating yield parser PG is NP-complete.
Proof. The optimal execution time of a yield parser PG with width(G ) = 0 is O(n2 ). This is clear,
since when all parsers are tabulated, the dependence graph is empty. Circuits in the corresponding dependence graph, arising from non-tabulated productions, represent table configurations that
lead to suboptimal runtimes of at least O(n3 ). Therefore, in order to obtain optimal runtime for the
algorithm, the dependence graph must be made cycle free. Achieving this by the minimal number
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
1339
of tables is equivalent to the node-deletion problem for acyclicity of a directed graph. And this is,
as expected, also NP-complete [18].
In the course of proving Theorems 3 and ??, we have restricted the yield grammars considered.
Our results, however, pertain to general yield grammars as well, because (1) arbitrary yield grammars
contain the restricted ones as a subclass, such that their table design problem is at least NP-hard.
(2) Testing goodness or optimality of a given table configuration works as described earlier also in
the general case, hence NP-completeness is retained.
3.4. A pragmatic implementation strategy
Motivated by the above NP-completeness results, we present a pragmatic approach to the table
design problem. It uses annotations by the programmer, preprocessing analyses, and a brute force
algorithm.
The programmer’s annotation distinguishes between two types of nonterminal symbols: the ones
that shall be tabulated, and the ones that shall be implemented as nontabulated recursive functions.
We denote them Ï‘a and a , respectively.
Similarly, we consider two additional sets of nonterminals, Ï‘p and p , derived from preprocessing phases. We use different phases, depending on whether we search for good or for optimal
configurations:
Good configurations. Productions having more than one self-reference need to be tabulated in
V {v}
any case: ϑp = {v|v ∈ V , (G(PG
)) > 1}. Conversely, nonterminals not contained in any circuit can by no means be responsible for exponential runtime: p = {v|v ∈ V , (v) = 0} with G =
a
p
G(PGϑ ∪ϑ ).
Optimal configurations. We derive the best possible polynomial degree by calculating the runtime for a full table configuration: ropt = r(PGV , n) (see Theorem 1). When not tabulated, even a
single self-recursive production or a production containing an inner loop can be responsible for
an additional runtime factor. We identify these candidates and mark them for tabulation: Ï‘p =
V {v}
, n) > ropt }. Clearly, nonterminals with a constant runtime need no tabulation:
{v|v ∈ V , r(PG
p
= {v|v ∈ V , r(ϑa ∪ ϑp , v, n) = O(1)}.
The remaining nonterminals are free for optimization by the brute force approach: F = V {ϑa ∪
a
∪ ϑp ∪ p }. Let be a predicate on table configurations that determines whether the configuration is relevant for optimization at all. Corresponding to Theorem 2, we use (ϑ) = (G(PGϑ )) 1
for good configurations and (ϑ) = r(PGϑ , n) ≡ ropt for the optimal ones.
Let ϑi = ϑa ∪ ϑp be the initial configuration. Then, = {ϑ ∪ ϑi |ϑ ∈ P (F), (ϑ ∪ ϑi )} describes
the set of configurations satisfying the predicate and min = {ϑ|ϑ ∈ , |ϑ| = minc∈ |c|} describes
the corresponding minimal configurations. Our brute force algorithm actually enumerates these
sets and tests for minimality.
Should this strategy not be effective (due to computational effort for min ), one must restart
with a more detailed annotation by the programmer.
In the implementation, we must also deal with inner loops arising from productions with width(v)
1, which played no role in the NP completeness proofs. During the construction of the dependence
graphs we represent dependences from inside inner loops by two edges instead of a single one. Since
Fig. 3. Dependence graph for pknotsRG—manual table design (17 tables). This table configuration leads to time and space requirements of O(n4 ) and
O(n2 ). The tabulated nonterminals are shown as nodes in dotted ovals; their calling arcs are also dotted.
1340
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
Fig. 4. Dependence graph for pknotsRG—good table design (4 tables). This table configuration leads to time and space requirements of O(n7 ) and
O(n2 ), respectively. Albeit polynomial, the runtime of O(n7 ) is surely unacceptable for practical usage.
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
1341
Fig. 5. Dependence graph for pknotsRG—optimal table design (12 tables). This table configuration leads to time and space requirements of O(n4 ) and
O(n2 ), respectively, the same as the manual design, but uses only about 70% of the table space.
1342
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
1343
our testing criterion is (G) 1, this ensures that all configurations with circuits containing an
inner loop are rejected.
3.5. Practical experience
The table design problem studied here mathematically arises in practice only when the algorithmic
task at hand has a certain minimal level of sophistication. To support our claim of practical relevance, we give a short report on such an application. Our largest ADP-program so far is pknotsRG
[25,23], which predicts RNA secondary structures including the so-called pseudoknots. Its time and
space requirements are O(n4 ) and O(n2 ). It uses a yield grammar with 47 nonterminal symbols. The
productions split up in a total of 140 alternatives, which indicates the complexity of the case analysis
involved. Therefore, space does not permit to explain the algorithm here. We show the dependence
graphs for three different table configurations in Figs. 3 – 5. The original implementation (Fig. 3)—
developed using manual table design—has a configuration of 17 tables. With moderate annotation,
our strategy derived good configurations of 4 tables (Fig. 4) and optimal configurations of 12 tables
(Fig. 5).
Comparing the hand-made to the optimal design, we found that while saving nearly 30% space,
the runtime of the optimized implementation increased by 19%—the constant factor due to the additional recursive function calls. In many applications in the bioinformatics domain, including this
one, available space is the limiting factor. In such cases, one is thankful to accept a small slowdown
in exchange for the ability to handle larger input data.
4. Conclusion
The main difficulty in the traditional development of dynamic programming algorithms can
be seen in the lack of a systematic approach for the definition of suitable recurrence equations.
The ADP approach and its associated program development discipline [13] alleviate these difficulties somewhat, but also shed light on a deeper challenge. We have shown that the algorithm
designer—whenever the algorithm is nontrivial and space usage is an issue—has to solve an
NP-complete design problem. He does so explicitly within the ADP framework, and implicitly
in the more traditional approach to dynamic programming. Although a human is not limited
by the laws of computational complexity, we still may take our result as the indicator of an
intrinsic difficulty in the design of dynamic programming algorithms. What has been shown
here using the ADP framework pertains prima facie to dynamic programming over sequential
data, but it may well hold for dynamic programming in general. It is unlikely that dynamic
programming over more structured data (trees, graphs, etc. ) should have a simpler table design
problem.
The efficiency analysis we are trying to automate and the complexity result attained for this
problem must not be mistaken to imply complexity results about particular application problems.
When our algorithm determines that a dynamic programming problem P , specified in algebraic
style, has an optimal table configuration of k tables leading to runtime O(nr ), this does not imply
that problem P cannot be solved faster than in O(nr ). Maybe P can be solved by other algorithmic
approaches, and a table design problem does not arise at all.
1344
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
Our pragmatic table design algorithm described above performs well on the largest problem instances we have encountered so far. It demonstrates that there are significant time-space trade-offs,
whose systematic exploitation is yet to be studied in more detail. However, it is certainly not the
only, and probably not the best approach. In our project mentioned earlier, where yield grammars
are to be generated automatically from the data (the evaluation algebra is fixed for all these grammars), we now have the obligation to also generate some “user” annotation required to make our
approach practical. An alternative would be to give up user annotation and optimality, and instead
develop an approximation scheme for the table design problem.
Acknowledgment
We are grateful to Marc Rehmsmeier for a careful reading of this manuscript.
References
[1] A. Aho, J. Ullman, The Theory of Parsing, Translation and Compiling, Prentice-Hall, Englewood Cliffs, NJ, 1973.
[2] A. Aho, J. Hopcroft, J. Ullman, Data Structures and Algorithms, Addison-Wesley, Reading, MA, 1982.
[3] V. Bafna, N. Edwards, On de novo interpretation of tandem mass spectra for peptide identification, in: Proceedings
of the Seventh Annual International Conference on Computational Molecular Biology, ACM Press, New York,
2003, pp. 9–18.
[4] R. Bellman, Dynamic Programming, Princeton University Press, Princeton, NJ, 1957.
[5] R. Bellman, S. Dreyfus, Applied Dynamic Programming, Princeton University Press, Princeton, NJ, 1962.
[6] H. Bodlaender, J. Telle, Space-efficient construction variants of dynamic programming, Nordic J. Comput. 11 (4)
(2004) 374–385.
[7] W. Brainerd, Tree generating regular systems, Inform. Control 14 (1969) 217–231.
[8] G. Brassard, P. Bratley, Algorithmics: Theory and Practice, Prentice-Hall, Englewood Cliffs, NJ, 1988.
[9] T. Cormen, C. Leiserson, R. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990.
[10] E.W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 (1959) 269–271.
[11] R. Durbin, S. Eddy, A. Krogh, G. Mitchison, Biological Sequence Analysis, Cambridge University Press, Cambridge,
MA, 1998.
[12] R. Giegerich, A systematic approach to dynamic programming in bioinformatics, Bioinformatics 16 (2000) 665–677.
[13] R. Giegerich, C. Meyer, P. Steffen, A discipline of dynamic programming over sequence data, Sci. Comput. Program.
51 (3) (2004) 215–263.
[14] D. Gusfield, Algorithms on Strings, Trees, and Sequences, Computer Science andComputational Biology, Cambridge
University Press, Cambridge, MA, 1997.
[15] D. Hirschberg, A linear space algorithm for computing maximal common subsequences, Commun. ACM 18 (6)
(1975) 341–343.
[16] R.M. Karp, R.E. Miller, S. Winograd, The organization of computations for uniform recurrence equations, J. ACM
14 (3) (1967) 563–590.
[17] D.E. Knuth, A generalization of Dijkstra’s algorithm, Inform. Process. Lett. 6 (1) (1977) 1–5.
[18] J.M. Lewis, M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System
Sci. 20 (2) (1980) 219–230.
[19] Y. Liu, S. Stoller, Program optimization using indexed and recursive data structures, in: PEPM ’02: Proceedings of
the 2002 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, ACM
Press, New York, NY, 2002, pp. 108–118.
[20] K. Mehlhorn, Data Structures and Algorithms, Springer-Verlag, New York, 1984.
[21] E. Myers, W. Miller, Optimal alignment in linear space, Comput. Appl. Biosci. 4 (1) (1988) 11–17.
P. Steffen, R. Giegerich / Information and Computation 204 (2006) 1325–1345
1345
[22] in: L. Pachter, B. Sturmfels (Eds.), Algebraic Statistics for Computational Biology, Cambridge University Press,
Cambridge, MA, 2005.
[23] J. Reeder, R. Giegerich, Design, implementation and evaluation of a practical pseudoknot folding algorithm based
on thermodynamics, BMC Bioinformatics, 5 (104) (2004), in press.
[24] G. Rote, Path problems in graphs, in: in: G. Tinhofer, E. Mayr, H. Noltemeier, M. Syslo (Eds.), Computational Graph
Theory, Computing Supplementum, vol. 7, Springer-Verlag, New York, 1990, pp. 155–189.
[25] A. Sczyrba, J. Krüger, H. Mersch, S. Kurtz, R. Giegerich, RNA-related tools on the bielefeld bioinformatics server,
Nuclic Acids Res. 31 (13) (2003) 3767–3770.
[26] R. Sedgewick, Algorithms, Second ed., Addison-Wesley, Reading, MA, 1989.
[27] R.E. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput. 1 (2) (1972) 146–160.
Installation Manual
Manual de Instrucciones
Manuel D’Installation
CST423SF
CST424SF(G)
CST743S
CST744S(G)
CST744SL
CST744SF.10
CST754SF(N)
CST784SF
MS756204SF
Warranty Registration and Inquiry
For product warranty registration, TOTO U.S.A. Inc. recommends online warranty registration. Please visit
our web site http://www.totousa.com. If you have questions regarding warranty policy or coverage, please contact TOTO U.S.A. Inc., Customer Service Department, 1155 Southern Road, Morrow, GA 30260
(888) 295-8134 or (678) 466-1300 when calling from outside of U.S.A.
Thanks for Choosing TOTO®! ������������������������������������������������������������������������������������������� 3
Before Installation ��������������������������������������������������������������������������������������������������������������� 3
Common Tools Needed ���������������������������������������������������������������������������������������������������� 3
Included Parts ��������������������������������������������������������������������������������������������������������������������� 3
Before Installation ��������������������������������������������������������������������������������������������������������������� 4
Installation Procedure �����������������������������������������������������������������������������������������������������4-6
Toilet Tank Fill Valve Instructions ������������������������������������������������������������������������������������6-7
Care and Cleaning �������������������������������������������������������������������������������������������������������������� 7
Warranty ������������������������������������������������������������������������������������������������������������������������������ 8
Rough-In Dimensions ������������������������������������������������������������������������������������������������������ 21
Replacement Parts ������������������������������������������������������������������������������������������������������������ 22
THANKS FOR CHOOSING TOTO!
The mission of TOTO is to provide the world with healthy, hygienic and more
comfortable lifestyles. We design every product with the balance of form and function
as a guiding principle. Congratulations on your choice.
COMMON TOOLS NEEDED
• 10” adjustable wrench
• Hacksaw
• Carpenter’s Level
•
•
•
•
Tape Measure
Pliers
Screwdriver
Putty Knife
MATERIALS REQUIRED:
• Flexible Supply Tube / Connector
• Mounting (T) Bolts & Nuts (2pc)
• Supply Stop Valve
• Wax Ring / Seal
INCLUDED PARTS
Check to make sure you have all these parts from the package:
China Bowl
China Tank Lid
China Tank
Tank to Bowl Hardware:
Tank to Bowl Gasket
Flange Caps (for the Bowl):
Bolts
(2 pieces)
Rubber Washers
(2 pieces)
Plastic Caps
(2 pieces)
Metal Washers
(4 pieces)
Nuts
(4 pieces)
Base Caps
(2 pieces)
3
ENGLISH
TABLE OF CONTENTS
BEFORE INSTALLATION
 Read these instructions thoroughly before beginning work.
 Please leave these instructions for customers. These instructions contain maintenance and warranty information.
 If necessary, remove the existing toilet.
ENGLISH
IMPORTANT!
Due to the powerful performance of our Cyclone, G-Max, E-Max and Power Gravity
flushing systems, they are not specified for back-to-back installations. The only
means of installing these toilets in a back-to-back situation is when the toilet drain
connections incorporate a WYE fitting. Please contact your builder or contractor prior
to this installation.
Double Combination WYE / 1/8 Bend
YES
Double Sanitary Tee / Sanitary Cross
NO
For your new TOTO toilet to fit correctly the rough-in, the distance between the
finished wall to the center of the closet flange, must be at least 12 inches for most
models. Models with 10” rough-in have model numbers ending with “.10”, for
example C744EF.10.”
Finished Wall
C/L
Supply
Valve
Closet
Flange
“RI”
INSTALLATION PROCEDURE
1) Clean any debris out of the closet flange and then
install new mounting bolts (not supplied) into the
slots of the closet flange (see Ill. 1). The head of the
bolt should be inserted into the slot with its threads
facing upward.
2) Carefully turn the toilet upside down onto some
padding. Firmly press a new bowl wax ring (not
supplied) onto the circular recess around the toilet
bowl’s horn (see Ill. 2). Turn the toilet upright and
gently lower into position over the closet flange.
With toilet properly aligned, press firmly on both
sides of toilet rim to set the bowl wax ring.
CAUTION: Do not move the bowl after the bowl
wax ring is set. Thread nuts and tighten evenly
until bowl is snug to closet flange. Install the bolt
caps.
CAUTION: Do not over-tighten the nuts as damage
to the china bowl may result.
4
Ill. 1
Ill. 2
Wax Ring
Horn
Installation Procedures (continued)
N OTE: The toilet bowl has three points of contact, which will actually contact the bottom of the
toilet tank when properly installed. The location of these points can be seen on the bowl at the
tank receiving area. The three points are front left (1), front right (2), and back center (3). Recall
these three points during the Toilet Tank installation.
Bolt Cap
Nut *
Washer *
Base Cap
2
1
3
Bowl Base
4) Place the tank upside down onto some
padding. Inspect the smaller fill valve nut
and larger flush valve nut for a secure connection.
Try to tighten the nuts with your hands see
Ill. 3). If loose, tighten the nut hand tight
and an additional 1/4 turn for the smaller fill
valve nut and an additional 1/2 turn for the
larger flush valve nut.
Place the tank-to-bowl gasket onto the
flush valve nut. While pressing down,
spread the gasket over the nut until the
gasket touches the bottom of the tank. A
slight gap between the tank bottom and
the gasket is allowable.
6) Pick up the tank and carefully guide the
brass bolts to align the tank with the bowl.
Attach a metal washer and nut to each bolt.
Tighten the nuts finger tight and inspect
that the tank is level (see Ill. 5). Once level,
tighten the bolts equally until the tank
makes THREE POINTS OF CONTACT with
the bowl.
5
Flush Valve
Nut
Fill Valve Nut
Tank to Bowl Gasket
Ill. 4
Metal Washer
Rubber Washer
T
CU
5) Lay the tank down on its back. Place a rubber washer onto a brass bolt. Reach inside
the tank and position the bolt through one
of the holes in the bottom of the tank (see
Ill. 4).
On the outside of the tank, place a metal
washer and nut onto the bolt. Hold the bolt
centered in the hole and tighten the nut
finger tight. Turn the nut an additional 1/2
turn with a wrench. Repeat this process for
the remaining hole in the tank.
Ill. 3
Nut
Bolt
AW
AY
VIE
W
Ill. 5
YES
NO
1&2
3
1&2
3 GAP
NO
3
1 & 2 GAP
ENGLISH
Three Points of Contact
Installation Procedures (continued)
ENGLISH
6) Flush the water supply line for a few seconds to
remove any debris that may enter the new fill valve.
(For new home constructions and/or additions, flush
the water supply line for more than a minute to help
remove any residual PVC adhesives, solder flux, and/or
pipe sealants that were used for the new plumbing.)
C
onnect the water supply line to the fill valve threads
as seen at the bottom of toilet tank (see Ill. 5). Tighten
this connection finger tight and then an additional 1/4
turn by hand. AVOID using a wrench to tighten the
connection as you may damage the plastic threads
and/or cause the fill valve to rotate inside the tank.
Water Supply Line Pressure should be 20 to 80 psi
Static.
N OTE: NO BALLCOCK / FILL VALVE ADJUSTMENTS
NEEDED. Water will automatically stop at the proper
level. Flush the toilet several times. Check the flapper valve for proper operation. Make sure that the
chain is not tangled and the flapper arm is in its
proper position.
Ill. 5
7/8” BALLCOCK
THREAD
HAND TIGHTEN
1/4 TURN ONLY
Ill. 6
7) I nstall the toilet tank lid onto the toilet tank
top.
Cap
Seat Hinge
8) I nstall the toilet seat onto the toilet bowl using
the mounting hardware in the toilet seat box
(see Ill. 6). Place seat onto bowl and rotate the
hinge down. Position seat stoppers under the
seat hinge.
I nsert bolt into seat hinge and through the
toilet bowl. Install plastic nut onto bolt from
underneath. Tighten the bolt securely. Install
the seat bolt caps.
N OTE: Tighten the seat bolt until the hinge
is secure. The seat and lid will have slight
side to side movement which is normal. This
freedom of movement allows the seat to
SoftClose® without binding.
Plastic Bolt
Seat Stopper
Bowl
Plastic
Nut
Mounting Hardware
1
2
3
4
5
6
1 – Cap
2 – Plastic Bolt
3 – Seat Hinge
4 – Seat Stopper
5 – Toilet Bowl
6 – Plastic Nut
TOILET TANK FILL VALVE INSTRUCTIONS
Replacement Procedure
1) Shut off the water supply to the toilet.
2) Flush toilet and remove remaining water from tank with a sponge.
3) Remove the water supply connection at the fill valve.
4) Remove old fill valve and use damp sponge to clean hole in tank.
5) Place new fill valve inside tank hole.
6) Thread mounting nut onto fill valve shank and tighten the nut.
N OTE: Do not over-tighten. Be sure to install fill valve in a position that does not
interfere with the trip lever operation.
6
Replacement Procedure (continued)
7) Connect water supply to fill valve shank and hand-tighten only.
NO TE: Do not overtighten. These are plastic parts. Never use pipe dope on any
water supply connection.
9) Turn water supply ON and check for leaks outside the tank.
NO TE: As water fills the tank, water is also directed into the overflow tube via the
refill tube. This additional flow of water is critical to refilling your toilet’s bowl.
Once the water stops filling the tank, some residual drops of water may drip
from the fill valve. This is NORMAL as these drops will subside.
Water Level Adjustment
Depending on the manufacturing plant, you may have one of two of the following fill
valves:
Type A
Type B
Water Level
For Type A Fill Valve:
Refer to the water level (WL) setting marked
on the inner wall of the tank. Allow the water to fill the tank. Turn the adjustment screw
clockwise in the (+) direction to increase the
water level height (see Illustration 1). Turn
the adjustment screw counter-clockwise in
the (-) direction to decrease the water level
height. Flush the toilet to verify the correct
water level. Adjust as necessary.
Ill. 1
Water
Level
Top of
Overflow
Tube
For Type B Fill Valve:
There are no water level adjustments. The
fill valve has been preset at the factory.
CARE AND CLEANING
WARNING!
DO NOT USE IN-TANK BOWLCLEANERS.
The use of high concentration of chlorine or chlorine-related products can seriously
damage fittings in the tank. This damage can cause leakage and property damage.
TOTO® shall not be responsible or liable for any tank fitting failure or damage caused
by the use of in-tank bowl cleaners.
7
ENGLISH
8) A
ttach refill tube to fill valve nipple and clip other end of refill tube to the overflow
pipe.
WARRANTY
ENGLISH
1. T
OTO warrants its vitreous china products (“Product”) to be free from defects in materials
and workmanship during normal use when properly installed and serviced, for a period of one
(1) year from date of purchase. This limited warranty is extended only to the ORIGINAL PURCHASER of the Product and is not transferable to any third party, including but not limited to
any subsequent purchaser or owner of the Product. This warranty applies only to TOTO Product
purchased and installed in North, Central and South America.
2. TOTO’s obligations under this warranty are limited to repair, replacement or other appropriate adjustment, at TOTO’s option, of the Product or parts found to be defective in normal
use, provided that such Product was properly installed, used and serviced in accordance with
instructions. TOTO reserves the right to make such inspections as may be necessary in order to
determine the cause of the defect. TOTO will not charge for labor or parts in connection with
warranty repairs or replacements. TOTO is not responsible for the cost of removal, return and/
or reinstallation of the Product.
3. This warranty does not apply to the following items:
a. Damage or loss sustained in a natural calamity such as fire, earthquake, flood, thunder,
electrical storm, etc.
b. Damage or loss resulting from any accident, unreasonable use, misuse, abuse, negligence, or improper care, cleaning, or maintenance of the Product.
c.
Damage or loss resulting from sediments or foreign matter contained in a water system.
d. Damage or loss resulting from improper installation or from installation of the Product in
a harsh and/or hazardous environment, or improper removal, repair or modification of the
Product. (NOTE: Product model codes allow a maximum of 80 PSI. Check local codes or
standards for requirements).
e. Damage or loss resulting from electrical surges or lightning strikes or other acts which are
not the fault of TOTO or which the Product is not specified to tolerate.
f. Damage or loss resulting from normal and customary wear and tear, such as gloss reduction, scratching or fading over time due to use, cleaning practices or water or atmospheric
conditions.
g.
Tank flushing mechanisms of plastic or rubber moving parts.
h.
Toilet seats of plastic, wood or metal.
4. In order for this limited warranty to be valid, proof of purchase is required. TOTO encourages
warranty registration upon purchase to create a record of Product ownership at http://www.
totousa.com. Product registration is completely voluntary and failure to register will not diminish your limited warranty rights.
5. THIS WARRANTY GIVES YOU SPECIFIC LEGAL RIGHTS. YOU MAY HAVE OTHER RIGHTS
WHICH VARY FROM STATE TO STATE, PROVINCE TO PROVINCE OR COUNTRY TO COUNTRY.
6. T
o obtain warranty repair service under this warranty, you must take the Product or deliver it
prepaid to a TOTO service facility together with proof of purchase (original sales receipt) and a
letter stating the problem, or contact a TOTO distributor or products service contractor, or write
directly to TOTO U.S.A., INC., 1155 Southern Road, Morrow, GA 30260 (678) 466-1300 or (888)
295-8134, if outside the U.S.A. If, because of the size of the Product or nature of the defect, the
Product cannot be returned to TOTO, receipt by TOTO of written notice of the defect together
with proof of purchase (original sales receipt) shall constitute delivery. In such case, TOTO may
choose to repair the Product at the purchaser’s location or pay to transport the Product to a
service facility.
WARNING! TOTO shall not be responsible or liable for any failure of, or damage to, this Product caused by either chloramines in the treatment of public water supply or cleaners containing
chlorine (calcium hypochlorite). NOTE: The use of a high concentrate chlorine or chlorine related
products can seriously damage the fittings. This damage can cause leakage and serious property
damage.
THIS WRITTEN WARRANTY IS THE ONLY WARRANTY MADE BY TOTO. REPAIR, REPLACEMENT
OR OTHER APPROPRIATE ADJUSTMENT AS PROVIDED UNDER THIS WARRANTY SHALL BE
THE EXCLUSIVE REMEDY AVAILABLE TO THE ORIGINAL PURCHASER. TOTO SHALL NOT BE
RESPONSIBLE FOR LOSS OF THE PRODUCT OR FOR OTHER INCIDENTAL, SPECIAL OR CONSEQUENTIAL DAMAGES OR EXPENSES INCURRED BY THE ORIGINAL PURCHASER, OR FOR
LABOR OR OTHER COSTS DUE TO INSTALLATION OR REMOVAL, OR COSTS OF REPAIRS BY
OTHERS, OR FOR ANY OTHER EXPENSE NOT SPECIFICALLY STATED ABOVE. IN NO EVENT
WILL TOTO’S RESPONSIBILITY EXCEED THE PURCHASE PRICE OF THE PRODUCT. EXCEPT TO
THE EXTENT PROHIBITED BY APPLICABLE LAW, ANY IMPLIED WARRANTIES, INCLUDING THAT
OF MERCHANTABILITY OR FITNESS FOR USE OR FOR A PARTICULAR PURPOSE, ARE EXPRESSLY DISCLAIMED. SOME STATES DO NOT ALLOW LIMITATIONS ON HOW LONG AN IMPLIED
WARRANTY LASTS, OR THE EXCLUSION OR LIMITATION OF INCIDENTAL OR CONSEQUENTIAL DAMAGES, SO THE ABOVE LIMITATION AND EXCLUSION MAY NOT APPLY TO YOU.
8
ÍNDICE
¡GRACIAS POR ELEGIR TOTO!
La misión de TOTO es dar al mundo estilos de vida más saludables, higiénicos y
cómodos. Diseñamos cada producto guiándonos por el principio del equilibrio entre
forma y función. Felicitaciones por su elección.
HERRAMIENTAS QUE NECESITA
• Llave Adjustable de 10”
• Sierra para Metales
• Nivel de Carpintero
•
•
•
•
Pinzas
Cinta para Medir
Destornillador
Espátula para Masilla
MATERIALES NECESARIOS:
• Tubo Abastecedor / Conector
• Pernos de Montaje (Cantidad 2)
• Sello / Anillo de Cera
• Tope de Suministro
INCLUÍA PARTES
Asegúrese de que tiene todas las piezas del empaque:
Recipiente Porcelana
Tapa del Tanque
Porcelana
Tanque Porcelana
Empaquetadura
Tanque – Recipiente
Tapas de la Brida
(Para el Recipiente):
Herrajes pra el Tanque y Recipiente:
Pernos
(2 piezas)
Rondanas Goma
(2 piezas)
Tapas Plástica
(2 piezas)
Rondanas Metálicos
(4 piezas)
Tuercas
(4 piezas)
Base Plástica
(2 piezas)
9
ESPAÑOL
¡Gracias Por Elegir TOTO®! ����������������������������������������������������������������������������������������������� 9
Antes de la Instalación ������������������������������������������������������������������������������������������������������� 9
Herramientas Necesarias Común ������������������������������������������������������������������������������������� 9
Incluía Partes ����������������������������������������������������������������������������������������������������������������������� 9
Antes de la Instalación ����������������������������������������������������������������������������������������������������� 10
Procedimiento de Instalación ������������������������������������������������������������������������������������� 10-12
Instrucciones Para la Instalación de la Válvula de Llenado del Tanque
de la Cisterna �������������������������������������������������������������������������������������������������������������� 12-13
Cuidado y Limpieza ���������������������������������������������������������������������������������������������������������� 13
Garantía ����������������������������������������������������������������������������������������������������������������������������� 14
Dimensiones Preliminares ������������������������������������������������������������������������������������������������ 21
Refacciones ����������������������������������������������������������������������������������������������������������������������� 22
ANTES DE LA INSTALACIÓN
 Lea estas instrucciones detenidamente antes de comenzar a trabajar.
 Proporcione las instrucciones a los clientes. Estas instrucciones contienen información sobre el mantenimiento y la garantía.
 Si es necesario, quite el inodoro existente.
¡IMPORTANTE!
Debido a la potente rendimiento de nuestro Ciclón, G-Max, S-Max y la gravedad de
alimentación de agua corriente, no se precisan para las instalaciones de “back-toback”. La única forma de instalar estos baños en una situación de “back-to-back“es
cuando las conexiones del desagüe WC incorporar un accesorio estrella. Por favor,
póngase en contacto con su constructor o contratista antes de esta instalación.
ESPAÑOL
Doble Combinación WYE / 1/8 Curva
Doble Sanitarias T / Sanitarias Cruz
SÍ
NO
Con el fín que su nuevo inodoro TOTO se adapte correctamente, la fontanería gruesala, distancia
desde la pared hasta el centro de la brida del suelo, debe ser al menos 12 pulgadas para la
mayoría de los modelos. Modelos con gruesala fontanería 10 pulgada tienen números de
modelo que terminan en “0.10”, por ejemplo C744EF.10.
Pared
C/L
Válvula de
Suministro
Brida del
Suelo
“RI”
PROCEDIMIENTO DE INSTALACIÓN
1) Limpie la suciedad de la brida del suelo, luego instale
los nuevos pernos de montaje (no suministrados) en
las ranuras de la brida del suelo (ver Ill. 1). La cabeza
del perno debe insertarse en la ranura con el vástago
roscado apuntando hacia arriba.
2) Dé vuelta al inodoro con mucho cuidado de modo
que quede mirando hacia abajo sobre un acolchonado. Presione firmemente un nuevo anillo de cera
de recipiente (no suministrado) sobre el encastre
circular alrededor de la apertura de salida (ver Ill. 2).
Levante el inodoro en dirección vertical y suavemente
bájelo hasta colocarlo sobre la brida del suelo. Con el
inodoro debidamente alineado, presione firmemente
a ambos lados el borde del inodoro para fijar el anillo
de cera del recipiente.
PRECAUCIÓN: No mueva el recipien te una vez
haya fijado el anillo de cera. Enrosque las tuercas y
aprietélas igualmente hasta que el inodoro quede
ajsutado a la brida del suelo. Instale las tapas de los
pernos.
PRECAUCIÓN: No ajuste demasiado las tuercas, podría ocasionar daños en la.
10
Ill. 1
Ill. 2
Anillo de
Cera
Horn
Procedimiento de Instalación (continuación)
N OTA: El recipiente del inodoro tiene tres puntos de contacto, los cuales deberán tocar la parte
de abajo del tanque cuando se es instalado debidamente. La ubicación de estos puntos puede
ser vista en la parte del recipiente donde debe ir el tanque. Los tres puntos son delantero
izquierdo (1), delantero derecho (2), y tracero central (3). Recuerde estos tres puntos cuando esté
instalando el tanque. en la parte del recipiente donde debe ir el tanque. Los tres puntos son
delantero izquierdo (1), delantero derecho (2), y tracero central (3). Recuerde estos tres puntos
cuando este instalando el tanque.
Tres Puntos de Contacto
Tapa
2
1
3
Bowl del
Recipiente
Ill. 3
6) Levante el tanque y cuidadosamente guíe los
pernos metálicos para alinear el tanque con el
recipiente. Fije una rondana metálica y una tuerca
a cada perno. Apriete las tuercas con sus dedos e
inspeccione que el tanque haya quedado nivelado
(ver Ill. 5). Una vez nivelado, apriete los pernos
igualmente hasta que el tanque haga TRES PUNTOS DE CONTACTO con el recipiente.
11
Empaquetadura Tanque-Recipiente
Ill. 4
Rondana
Metalica
Rondana de
Goma
Tuerca
Perno
C
N
5) Acueste el tanque sobre su parte trasera. Coloque una rondana de goma en el perno metálico.
Extienda su mano dentro del tanque y coloque el
perno a través de uno de los orificios del fondo
del tanque (ver Ill. 4).
En la parte de afuera del tanque, coloque una rondana metálica y una tuerca en el perno. Mantenga
el perno centrado en el orificio y apriete la turca
con sus dedos. Dé 1/2 vuelta adicional a la tuerca
con la llave para tubería. Repita este proceso para
el otro orificio del tanque.
Tuerca Valvula
de Vaciado
Tuerca Valvula de
Llenado
AE
VIS T
4) Dé vuelta al inodoro de modo que quede mirando
hacia abajo sobre algún acol chonado. Inspeccione la tuerca pequeña de la válvula de llenado
y la tuerca grande de la válvula de vaciado para
garantizar la conexión.
Trate de apretar las turcas con su mano (ver Ill. 3).
Si aún siguen holgadas, apriételas manual mente
y dé 1/4 de vuelta adicional a la tuer ca pequeña
de la válvula de llenado y 1/2 vuelta a la tuerca
grande de la válvula de vaciado.
Coloque la empaquetadura del tanque-recipiente
sobre la tuerca de la válvula de vaciado. Mientras
presiona hacia abajo, despliegue la empaquetadura sobre la tuerca hasta que esta toque el fondo
del tanque. Un pequeño espacio entre el fondo
del tanque y la empaquetadura está permitido.
O
RT
E
Ill. 5
SI
NO
1&2
3
1&2
3 GAP
NO
3
1 & 2 GAP
ESPAÑOL
Tuerca *
Rondana *
Base de la Tapa
Procedimiento de Instalación (continuación)
ESPAÑOL
6) D
escargue la línea de suministro de agua por algunos segundos para remover cualquier suciedad que haya entrado a la
nueva vávula de llenado. (Para construcciones nuevas y/o adiciones, descargue la línea de suministro de agua por más de 1
minuto para ayudar a remover cualquier residuo de adhesivo
de PVC, soldadura plástica, y/o sellantes de tubería que fueron
usados para la nueva tubería).
C
onecte la línea de suministro de agua a la rosca de la válvula
de llenado como se ve en la parte de abajo del tanque del
inodoro. Apriete esta conexión con sus dedos y luego dé
1/4 de vuelta adicional con la mano. Evite usar una llave para
tubería al apretar la tubería ya que esto podría dañar las roscas
plásticas y/o causar que la válvula de llenado rote dentro del
tanque La presion de la línea de suministro de agua debe ser
de 20 a 80 psi estática.
N OTA: NO ES NECESARIO AJUSTAR LA VÁLVULA DE RELLENO/LLAVE DEL FLOTADOR. El agua se tendrá al nivel
apropiado de forma automática. Tire la cadena varias veces.
Controle que la válvula de la cisterna funcione adecuadamente. Asegúrese de que la cadena no esté enredada y que
el brazo de la cisterna se encuentre en la posición correcta.
7) I nstale la tapa del tanque en el inodoro.
Ill. 6
8) I nstale el asiento del inodoro sobre el recipiente, usando los herrajes de montaje de la caja
Bisagra de
del asiento del inodoro (ver Ill. 6). Coloque la
la Silla
silla sobre el recipiente y rote la bisagra hacia
abajo. Posicione las piezas de restricción de la
silla debajo de las bisagras de la silla.
I ntroduzca el perno dentro de la bisagra de
la silla y a través del recipiente del inodoro.
Instale la tuerca plástica en el perno desde la
parte de abajo. Apriete los pernos asegurándolos. Instale las tapas.
N OTA: Apriete los pernos de la silla hasta
que la bisagra esté asegurada. La silla y la
tapa tendrán pequeños movimien tos de
lado a lado, esto es normal. Esta libertad de
movimiento permite que la silla SoftClose®
cierre sin que se golpee.
Ill. 5
7/8” ROSCA DEL
FLOTADOR APRETAR
MANUALMENTE 1/4 DE
VUELTA SOLAMENTE
Tapa
Perno Plastico
Piezas de Restriccion
Recipiente
Tuerca
Platica
Herrajes de Montaje
1
2
3
4
5
6
1 – Tapa
2 – Perno Plasticot
3 – Bisagra de la Silla
4 – Piezas de Restriccion
5 – Recipiente
6 – Tuerca Plastia
INSTRUCCIONES PARA LA INSTALACIÓN DE LA VÁLVULA
DE LLENADO DEL TANQUE DE LA CISTERNA
Procedimiento de Reemplazo
1)
2)
3)
4)
Cierre el suministro de agua al excusado.
Tire la cadena y retire el agua restante del tanque con una esponja.
Quite la conexión del suministro de agua de la válvula de llenado.
Quite la válvula de llenado anterior y utilice la esponja húmeda para limpiar el
orificio del tanque.
5) Coloque la válvula de llenado nueva en el orificio del tanque.
6) Enrosque la tuerca de montaje en el vástago de la válvula de llnado y ajuste la
tuerca.
N OTA: No ajuste demasiado. Asegúrese de instalar la válvula de llenado en una
posición que no interfiera con el funcionamiento de la palanca de descarga.
12
Ajuste del Nivel del Agua
Dependiendo de la planta de fabricación, usted debe tener una o ambas de las
siguientes válvulas de llenado:
Tipo A
Tipo B
Water Level
Para una Válvula de Llenado Tipo A:
Refere a la marca para el nivel de agua
(WL) en la pared interior del tanque.
Permita que el agua llene el tanque. Gire
el tornillo de ajuste en el sentido de las
agujas del reloj en la dirección (+) para
aumentar la altura del nivel del agua. (ver
Ilustración 1). Gire el tornillo en sentido
contrario a las agujas del reloj en la dirección (-) para disminuir la altura del nivel
del agua. Tire la cadena para verificar el
nivel correcto del ajuste si es necesario.
Ill. 1
Parte Superior del Tubo de
Rebosadero/
Tubo de Relleno
WL
Para la Válvula Tipo B:
No hay ajustes de niveles de agua. La
válvula de llanado nado se ha predeterminado de fábrica.
CUIDADO Y LIMPIEZA
AVISO: NO UTILICE LIMPIADORES EN EL RECIPIENTE DEL TANQUE
El uso de cloro en alta concentración o productos derivados del cloro puede dañar
seriamente los accesorios en el tanque. Este daño puede ocasionar fugas y daños en
la propiedad. TOTO® no se hará responsable por fallas o daños en los accesorios del
tanque causados por el uso de limpiadores en el recipiente del tanque.
13
ESPAÑOL
Procedimiento de Reemplazo (continuación)
6) Enrosque la tuerca de montaje en el vástago de la válvula de llnado y ajuste la
tuerca.
N OTA: No ajuste demasiado. Asegúrese de instalar la válvula de llenado en una
posición que no interfiera con el funcionamiento de la palanca de descarga.
7) Conecte el suministro de agua al vástago de la válvula de llenado y sólo ajústelo
manualmente.
N OTA: No ajuste demasiado. Éstas son piezas plásticas. No utilice lubricante en
ninguna conexión de suministro de agua.
8) Conecte el tubo de relleno al niple de la válvula y sujete el otro extremo del tubo
de relleno al tubo de desagüe.
9) Abra el suministro de agua y verifique que no haya pérdida de agua fuera del
tanque.
N OTA: A medida que el agua llene el tanque, también será derivada al tubo de
desagüe a travs del tubo de relleno. Este flujo de agua adicional es fundamental
para rellenar el recipiente del excusado. Una vez que el tanque está lleno y el
suministro de agua se interrumpe, es probable que caigan algunas gotas de agua
residual de la válvula de llenado. Esto es NORMAL y las gotas dejarán de caer.
GARANTÍA
ESPAÑOL
1. TOTO® garantiza que su vitreos china producto no presenta defectos en sus materiales ni de fabricación durante su uso normal cuando es instalado y mantenido adecuadamente, por un periodo
de uno (1) año(s) a partir de la fecha de compra. Esta garantía limitada es válida solamente para el
COMPRADOR ORIGINAL del Producto y no es transferible a una tercera persona, incluyendo, pero
sin limitarse a, cualquier comprador o propietario subsecuente del Producto. Esta garantía aplica
solamente al Producto TOTO comprado e instalado en América del Norte, Central, Latina y del Sur.
2. Las obligaciones de TOTO bajo esta garantía se limitan a la reparación, cambio o cualquier otro
ajuste, a petición de TOTO, del Producto o partes que resulten defectuosas en su uso normal,
siempre que dicho Producto haya sido instalado, utilizado y mantenido de acuerdo con las instrucciones. TOTO se reserve el derecho de hacer tantas inspecciones como sean necesarias para
determinar la causa del defecto. TOTO no cobrará por la mano de obra o partes relacionadas con
las reparaciones o cambios garantizados. TOTO no es responsable por el costo de la remoción,
devolución y/o reinstalación del Producto.
3. Esta garantía no aplica en los siguientes casos:
a) Daño o pérdida ocurrida en un desastre natural, tal como: incendio, sismo, inundación, relámpago, tormenta eléctrica, etc.
b) Daño o pérdida resultado de cualquier accidente, uso inaceptable, mal uso, abuso, negligencia o cuidado, limpieza o mantenimiento inadecuado del Producto.
c) Daño o pérdida causada por los sedimentos o material extraña contenida en un sistema de
agua.
d) Daño o pérdida causada por una mala instalación o por la instalación del Producto en un
ambiente duro y/o peligroso, o una remoción, reparación o modificación inadecuada del
Producto.
e) Daño o pérdida causada por sobrecargas eléctricas o rayos u otros actos que no sea responsabilidad de TOTO o que el Producto no esté especificado para tolerar.
f) Daño o pérdida causada por el uso normal y personalizado, tal como reducción del brillo,
rayado o pérdida de color en el tiempo debido al uso, prácticas de limpieza o condiciones
del agua o atmosféricas.
4. Para que esta garantía limitada sea válida, prueba de compra es necesaria. TOTO anima el registro
de la garantía sobre compra para cree un archivo de la propiedad del producto en http://www.
totousa.com. El registro del producto es totalmente voluntario y la falta a registrar no disminuirá
sus derechas de garantía limitada.
5. ESTA GARANTÍA LE DA DERECHOS LEGALES ESPECÍFICOS. USTED PODRÍATENER OTROS
DERECHOS QUE PUEDEN VARIAR DEPENDIENDO DEL ESTADO O PROVINCIA EN EL QUE SE
ENCUENTRE.
6. Para obtener el servicio de reparación de esta garantía, debe llevar el Producto o enviarlo prepagado a un modulo de servicios TOTO junto con la prueba de compra (recibo de compra original)
y una carta en la que plantee el problema, o póngase en contacto con un distribuidor TOTO o el
contratista de servicio de los productos, o escriba directamente a TOTO U.S.A., INC., 1155 Southern Road, Morrow, GA 30260 (678) 466-1300 o 888) 295-8134, si fuera de los E.E.U.U. Si, debido
al tamaño del producto o naturaleza del defecto, el Producto no puede ser devuelto a TOTO, la
recepción en TOTO del aviso escrito del defecto junto con la prueba de compra (recibo de compra
original) constituirá el envío. En tal caso, TOTO podrá escoger entre reparar el Producto en el domicilio del comprador o pagar el transporte del Producto a un módulo de servicio.
ESTA GARANTÍA ESCRITA ES LA ÚNICA GARANTÍA HECHA POR TOTO. LA REPARACIÓN, CAMBIO U OTRO AJUSTE ADECUADO, TAL COMO APARECE EN ESTA GARANTÍA, SERÁ EL ÚNICO
REMEDIO DISPONIBLE PARA EL COMPRADOR ORIGINAL. TOTO NO SERÁ RESPONSABLE POR
LA PÉRDIDA DEL PRODUCTO O POR CUALQUIER OTRO DAÑO ACCIDENTAL, ESPECIAL O CONSECUENTE O POR DAÑOS INCURRIDOS POR EL COMPRADOR ORIGINAL, O POR LA MANO DE
OBRA U OTROS COSTOS RELACIONADOS CON LA INSTALACIÓN O REMOCIÓN, O COSTOS
DE REPARACIONES HECHAS POR OTROS, O POR CUALQUIER OTRO GASTO NO INDICADO DE
MANERA ESPECÍFICA EN LOS PÁRRAFOS ANTERIORES. EN NINGÚN CASO LA RESPONSABILIDAD DE TOTO EXCEDERÁ EL PRECIO DE COMPRA DEL PRODUCTO. EXCEPTO EN LA MEDIDA
EN QUE QUEDE PROHIBIDO POR LA LEYAPLICABLE, TODA GARANTÍA IMPLÍCITA, INCLUYENDO
AQUELLAS DE COMERCIABILIDAD O IDONEIDAD DE USO PARA EL USO O PARA UN PROPÓSITO
PARTICULAR, ESTÁ EXPRESAMENTE PROHIBIDA. ALGUNOS ESTADOS NO PERMITEN LAS LIMITACIONES ACERCA DE LA DURACIÓN DE UNA GARANTÍATÁCITA, O LA EXCLUSIÓN O LIMITACIÓN
DE DAÑOS INCIDENTALES O CONSECUENTES, POR LO QUE LA LIMITACIÓN E INCLUSIÓN ANTERIORES PUEDEN NO APLICAR A USTED.
AVISO TOTO no será responsable de fallas o daños ocasionados en este producto de plomería o
componente del producto causados por cloraminas en el tratamiento del suministro de agua público
o en los limpiadores en el recipiente del tanque que contengan cloro (hipoclorito de calcio). Nota:
el uso de cloro en alta concentración o productos derivados del cloro puede dañar seriamente los
accesorios. Este daño puede ocasionar fugas y daños graves en la propiedad. Para obtener más información, llámenos al (888) 295-8134.
14
TABLE DES MATIÈRES
Merci d’Avoir Choisi TOTO®! ����������������������������������������������������������������������������������������� 15
Outils Communs Nécessaires ����������������������������������������������������������������������������������������� 15
Pièces Incluses ����������������������������������������������������������������������������������������������������������������� 15
Avant de Commencer ����������������������������������������������������������������������������������������������������� 16
Procédure d’Installation ���������������������������������������������������������������������������������������������16-18
Instructions du Robinet de Remplissage du Réservoir ��������������������������������������������18-19
Entretien et Nettoyage ��������������������������������������������������������������������������������������������������� 19
Garantie ������������������������������������������������������������������������������������������������������������…
Purchase answer to see full
attachment

  
error: Content is protected !!