1995-01-12
CiteSeerPSUset
Computing Eigenspaces with Specified Eigenvalues...
Bo Kagstrom
Peter Poromaa
Bo Kagstrom,Peter Poromaa Computing Eigenspaces with Specified Eigenvalues of a Regular Matrix Pair
Theory, algorithms and LAPACK--style software for computing a pair of deflating
subspaces with specified eigenvalues of a regular matrix pair (A; B) and error bounds
for computed quantities (eigenvalues and eigenspaces) are presented. The reordering
of specified eigenvalues is performed with a direct orthogonal transformation method
with guaranteed numerical stability. Each swap of two adjacent diagonal blocks in
the real generalized Schur form, where at least one of them corresponds to a complex
conjugate pair of eigenvalues, involves solving a generalized Sylvester equation and
the construction of two orthogonal transformation matrices from certain eigenspaces
associated with the diagonal blocks. The swapping of two 1 Theta 1 blocks is performed
using orthogonal (unitary) Givens rotations. The error bounds are based on estimates
of condition numbers for eigenvalues and eigenspaces. The software computes reciprocal
values of a condition number for an individual eigenvalue (or a clus...
The Pennsylvania State University CiteSeer Archives
unknown
1995-01-12
ps
http://citeseer.ist.psu.edu/154201.html
http://www.cs.utk.edu/~library/TechReports/1994/ut-cs-94-255.ps.Z
en
unrestricted
2002-03-20
CiteSeerPSUset
On the Maximum Average Degree...
A. Raspaud
LaBRI , Universit'e Bordeaux I , 33405 Talence , France
A. V. Kostochka
630090 , Novosibirsk , Russia
Institute of Mathematics
E. Sopena
LaBRI , Universit'e Bordeaux I , 33405 Talence , France
J. Nesetril
Prague , Czech Republic
Dept . of Appl . Math . , Charles University
O. V. Borodin
Nottingham , NG7 2RD , UK
Dept . of Math . , University of Nottingham
A. Raspaud,A. V. Kostochka,E. Sopena,J. Nesetril,O. V. Borodin On the Maximum Average Degree and the Oriented Chromatic Number of a Graph
The oriented chromatic number o(H) of an oriented graph H is defined as the
minimum order of an oriented graph H
such that H has a homomorphism to H
.
The Pennsylvania State University CiteSeer Archives
unknown
2002-03-20
ps
http://citeseer.ist.psu.edu/569016.html
http://www.labri.fr/Labri/Publications/Rapports-internes/RR-112496.ps.Z
en
unrestricted
2001-04-18
CiteSeerPSUset
On the Maximum Average Degree and ...
On the Maximum Average Degree and the Oriented Chromatic Number of a Graph
. The oriented chromatic number o(H) of an oriented graph H is dened as the minimum order of
an oriented graph H
0
such that H has a homomorphism to H
0
. The oriented chromatic number o(G) of an
undirected graph G is then dened as the maximum oriented chromatic number of its orientations. In this
paper we study the links between o(G) and mad(G) dened as the maximum average degree of the subgraphs
of G.
Keywords. Oriented graph colouring, Graph homomorphism, Maximum average degree.
1
The Pennsylvania State University CiteSeer Archives
unknown
2001-04-18
ps
http://citeseer.ist.psu.edu/447389.html
http://dept-info.labri.u-bordeaux.fr/~sopena/Papiers/Comprimes/bknrs99.ps.gz
en
unrestricted
1996-06-20
CiteSeerPSUset
On the Maximum Average Degree and ...
A. Raspaud,A. V. Kostochka,E. Sopena,J. Nesetril,O. V. Borodin On the Maximum Average Degree and the Oriented Chromatic Number of a Graph
The oriented chromatic number o(H) of an oriented graph H is defined as the
minimum order of an oriented graph H
0
such that H has a homomorphism to H
0
.
The oriented chromatic number o(G) of an undirected graph G is then defined as
the maximum oriented chromatic number of its orientations. In this paper we study
the links between o(G) and mad(G) defined as the maximum average degree of the
subgraphs of G.
1 Introduction and statement of results
For every graph G we denote by V (G), with vG = jV (G)j, its set of vertices and by E(G),
with e G = jE(G)j, its set of arcs or edges. A homomorphism from a graph G to a graph
On leave of absence from the Institute of Mathematics, Novosibirsk, 630090, Russia. With support
from Engineering and Physical Sciences Research Council, UK, grant GR/K00561, and from the
International Science Foundation, grant NQ4000.
y
This work was partially supported by the Network DIMANET of the European Union and by the
grant 96-01-01614 of the Russian F...
The Pennsylvania State University CiteSeer Archives
unknown
1996-06-20
ps
http://citeseer.ist.psu.edu/224016.html
ftp://ftp.labri.u-bordeaux.fr/pub/Local/Info/Publications/Rapports-internes/RR-112496.ps.Z
en
unrestricted
1997-05-26
CiteSeerPSUset
On the Maximum Average Degree and ...
A. Raspaud,A. V. Kostochka,E. Sopena,J. Nesetril,O. V. Borodin On the Maximum Average Degree and the Oriented Chromatic Number of a Graph
The oriented chromatic number o(H) of an oriented graph H is defined as the
minimum order of an oriented graph H
0
such that H has a homomorphism to H
0
.
The oriented chromatic number o(G) of an undirected graph G is then defined as
the maximum oriented chromatic number of its orientations. In this paper we study
the links between o(G) and mad(G) defined as the maximum average degree of the
subgraphs of G.
On leave of absence from the Institute of Mathematics, Novosibirsk, 630090, Russia. With support
from Engineering and Physical Sciences Research Council, UK, grant GR/K00561, and from the
International Science Foundation, grant NQ4000.
y
This work was partially supported by the Network DIMANET of the European Union and by the
grant 96-01-01614 of the Russian Foundation for Fundamental Research.
z
A part of this research was supported by GACR and GAUK grants and done during a visit of LaBRI,
Universit'e Bordeaux I ( France).
1 Introduction and statement of results
For e...
The Pennsylvania State University CiteSeer Archives
unknown
1997-05-26
ps
http://citeseer.ist.psu.edu/114377.html
http://www.labri.u-bordeaux.fr/Equipe/CombAlg/membre/sopena/PAPERS/bknrs-96.ps.gz
en
unrestricted
1996-09-01
CiteSeerPSUset
A New Proof Of The Four-Colour Theorem
And Robin Thomas
Communicated Ronald Graham
Daniel P. Sanders
Neil Robertson
Paul Seymour
And Robin Thomas,Communicated Ronald Graham,Daniel P. Sanders,Neil Robertson,Paul Seymour A New Proof Of The Four-Colour Theorem
. The four-colour theorem, that every loopless planar graph admits
a vertex-colouring with at most four different colours, was proved in 1976 by
Appel and Haken, using a computer. Here we announce another proof, still
using a computer, but simpler than Appel and Haken's in several respects.
1. Introduction
For our purposes a graph G consists of a finite set V (G) of vertices, a finite
set E(G) of edges, and an incidence relation between them. Each edge is incident
with two vertices, called its ends. An edge whose ends are equal is called a loop.
A plane graph is a graph embedded in the plane (without crossings, in the usual
way). The four-colour theorem (briefly, the 4CT) asserts that every loopless plane
graph admits a 4-colouring, that is, a mapping c : V (G) ! f0; 1; 2; 3g such that
c(u) 6= c(v) for every edge of G with ends u and v. This was conjectured by F.
Guthrie in 1852, and remained open until a proof was found by Appel and Haken
[3], [4], [5] in 1976.
Unfortunately, th...
The Pennsylvania State University CiteSeer Archives
unknown
1996-09-01
ps
http://citeseer.ist.psu.edu/372465.html
http://www.mpim-bonn.mpg.de/external-documentation/era-mirror/1996-01-003/1996-01-003.ps
en
unrestricted
1997-08-13
CiteSeerPSUset
Normalized Coprime Factorizations ...
J. W. Hoffmann
Kaiserslautern , Germany
Fachbereich Mathematik; Universitat Kaiserslautern
J. W. Hoffmann Normalized Coprime Factorizations in Continuous and Discrete Time - a Joint State-Space Approach
Based on state--space formulas for coprime factorizations over RH
1
+ and an algebraic
characterization of J--inner functions, normalized doubly--coprime factorizations
for different classes of continuous-- and discrete--time transfer functions are derived
by using a single general construction method. The parametrization of the factors
is in terms of the stabilizing solutions of general degenerate continuous-- respectively
discrete--time Riccati equations, which are obtained by examining state--space representations
of J--normalized factor matrices.
1 INTRODUCTION 2
1 Introduction
In this paper we study coprime factorizations of rational matrix--valued functions and
their representations in state--space form. In the scalar case, every rational function g
with coefficients in R can be represented as the quotient of two coprime polynomials p
and q; a characterization of coprimeness of p and q is available by checking the solvability
of the associated Bezout equation. For rational...
The Pennsylvania State University CiteSeer Archives
unknown
1997-08-13
ps
http://citeseer.ist.psu.edu/29509.html
http://kbibmp3.ub.uni-kl.de/Preprint/PS/bericht_129.ps.gz
en
unrestricted
1999-04-29
CiteSeerPSUset
The Reduced Genus of a Multigraph
Patrice Ossona De Mendez
54 Bd Raspail , 75006 Paris , France
CNRS UMR 0017 , E.H.E.S.S.
Patrice Ossona De Mendez The Reduced Genus of a Multigraph
. We dene here the reduced genus of a multigraph as the minimum
genus of a hypergraph having the same adjacencies with the same
multiplicities. Through a study of embedded hypergraphs, we obtain new
bounds on the coloring number, clique number and point arboricity of
simple graphs of a given reduced genus. We present some new related
problems on graph coloring and graph representation.
1 Introduction
Graph Coloring is a central topic in Graph Theory and numerous studies relate
coloring properties with the genus of a graph. The maximum chromatic number
among all graphs which can be embedded in a surface of genus g is given by
Heawood's formula [14], as established by Ringel and Youngs for g > 0 [22]; the
case g = 0, which is the Four Color Theorem, has been established by Appel
and Haken [1][2] (see [24] for a simpler proof). Other approaches have related
the chromatic number with other graph invariants: For instance, Szekeres and
Wilf [28] gave the simple upper bound (G) sw(G) + 1...
The Pennsylvania State University CiteSeer Archives
unknown
1999-04-29
ps
http://citeseer.ist.psu.edu/1967.html
http://www.ehess.fr/centres/cams/person/pom/./../../papers/174.ps.gz
en
unrestricted
1999-04-29
CiteSeerPSUset
Stretchability Of Jordan Arc ...
H. De Fraysseix
De Mendez,Fraysseix And,H. De,P. Ossona Stretchability Of Jordan Arc Contact Systems
. We prove that a necessary and suÆcient condition for a contact
system of Jordan arcs to be stretchable is to be extendable into a weak arrangement
of pseudo-lines.
1. Introduction
A Jordan arc is an arc homeomorphic to a straight line segment. A pseudo-line
is an arc homeomorphic to a straight line.
A contact system is a set of Jordan arcs in the plane, such that two arcs intersect
at most once at a point which is internal to at most one arc. A contact system
is stretchable if there exits an homeomorphism which transforms it into a contact
system whose arcs are straight line segments.
Denition 1.1. A set L = (L 1 ; : : : ; L k ) of pseudo-lines is a weak arrangement of
pseudo-lines if it satises :
8i 6= j; jL i L j j 1 (1)
Denition 1.2. A contact system A = (A 1 ; : : : ; A k ) is extendable into a weak
arrangement of pseudo-lines if there exists an arrangement of pseudo-lines (resp. a
weak arrangement of pseudo-lines) L = (L 1 ; : : : ; L k ), such that A i L i for eac...
The Pennsylvania State University CiteSeer Archives
unknown
1999-04-29
ps
http://citeseer.ist.psu.edu/186586.html
http://www.ehess.fr/centres/cams/person/hf/./../../papers/172.ps.gz
en
unrestricted
1995-01-12
CiteSeerPSUset
The Scotch Parallel Storage System
The Scotch Parallel Storage System
To meet the bandwidth needs of modern computer systems, parallel storage systems are evolving
beyond RAID levels 1 through 5. The Parallel Data Lab at Carnegie Mellon University has constructed
three Scotch parallel storage testbeds to explore and evaluate five directions in RAID evolution: first,
the development of new RAID architectures to reduce the cost/performance penalty of maintaining
redundant data; second, an extensible software framework for rapid prototyping of new architectures;
third, mechanisms to reduce the complexity of and automate error-handling in RAID subsystems;
fourth, a file system extension that allows serial programs to exploit parallel storage; and lastly, a parallel
file system that extends the RAID advantages to distributed, parallel computing environments. This
paper describes these five RAID evolutions and the testbeds in which they are being implemented and
evaluated.
http://www.cs.cmu.edu:8001/Web/Groups/PDL
The Scotch Parallel Storage Systems
Garth A....
The Pennsylvania State University CiteSeer Archives
unknown
1995-01-12
ps
http://citeseer.ist.psu.edu/118.html
http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pdl/ftp/SPFS/tr95-107.ps
en
unrestricted
1998-09-22
CiteSeerPSUset
Intersection Graphs of Jordan Arcs
H. De Fraysseix,P. Ossona De Mendez Intersection Graphs of Jordan Arcs
. A family of Jordan arcs, such that two arcs are nowhere tangent,
defines a hypergraph whose vertices are the arcs and whose edges are the
intersection points. We shall say that the hypergraph has a strong intersection
representation and, if each intersection point is interior to at most one arc, we
shall say that the hypergraph has a strong contact representation.
We first characterize those hypergraphs which have a strong contact representation
and deduce some sufficient conditions for a simple planar graph to
have a strong intersection representation.
Then, using the Four Color Theorem, we prove that a large class of simple
planar graphs have a strong intersection representation.
1. Introduction
A family of Jordan arcs, such that two arcs are nowhere tangent, defines a
hypergraph whose vertices are the arcs and whose edges are the intersection points.
We shall say that the hypergraph has a strong intersection representation and,
if each intersection point is interior to at most o...
The Pennsylvania State University CiteSeer Archives
unknown
1998-09-22
ps
http://citeseer.ist.psu.edu/173891.html
http://www.ehess.fr/centres/cams/person/hf/../../papers/146.ps.gz
en
unrestricted
1996-04-24
CiteSeerPSUset
Control Relevant Identification for ...
Paul M. J
Mechanical Engineering Systems and Control Group,; Delft University of Technology , Mekelweg 2 , 2628 CD Delft , The Netherlands.
Raymond A. De Callafon
Mechanical Engineering Systems and Control Group,; Delft University of Technology , Mekelweg 2 , 2628 CD Delft , The Netherlands.
Van Hof
Mechanical Engineering Systems and Control Group,; Delft University of Technology , Mekelweg 2 , 2628 CD Delft , The Netherlands.
Paul M. J,Raymond A. De Callafon,Van Hof Control Relevant Identification for ...-norm based Performance Specifications
In an iterative scheme of identification and model based control design, compatible
criteria in both the identification and the control design are a prerequisite during the
iterations involved, in order to ensure performance improvement of the unknown plant
to be controlled. In case of H1-norm based control design paradigms this unleashes
the need for an alternative identification criterion other than the classical (weighted)
H 2 -norm based criteria that are being used frequently. This report presents a procedure
for performing a control relevant and approximate identification of a possibly unstable
and feedback controlled plant by using an H1-norm based identification criterion. A
unified approach to handle both stable and unstable plants is obtained by estimating a
stable factorization of the plant, based on noisy frequency domain data obtained from
closed loop experiments. It will be shown that the H1-norm based criterion can be
handled by the parametrization of all stable factori...
The Pennsylvania State University CiteSeer Archives
unknown
1996-04-24
ps
http://citeseer.ist.psu.edu/34384.html
http://www-mr.wbmt.tudelft.nl/~callafon/n482.ps
en
unrestricted
1996-04-24
CiteSeerPSUset
A Unified Approach on Stability Robustness ...
Hof P. M. M. Bongers
Mechanical Engineering Systems and Control Group,; Delft University of Technology , Mekelweg 2 , 2628 CD Delft , The Netherlands.
P. M. J. Van
Mechanical Engineering Systems and Control Group,; Delft University of Technology , Mekelweg 2 , 2628 CD Delft , The Netherlands.
Hof P. M. M. Bongers,P. M. J. Van A Unified Approach on Stability Robustness for Uncertainty Descriptions based on Fractional Model Representations
The powerful standard representation for uncertainty descriptions in a basic perturbation
model as introduced in Doyle (1982) can be used to attain necessary and
sufficient conditions for stability robustness within various uncertainty descriptions.
In this paper these results are applied to uncertainty descriptions that are based on
fractional model representations. Special attention will be given to upper bounds on
additive coprime factor perturbations which could have been obtained by identification
techniques. Necessary and sufficient conditions for stability robustness will be derived
and compared with well known stability robustness results based on-gap and gap
metric distance measures. Based on this comparisment a result on conservatism is
presented here.
1 Introduction
In the research area of system identification and model based control design it is widely
recognized that models found by system identification and used for control design are necessarily
approximative. On the o...
The Pennsylvania State University CiteSeer Archives
unknown
1996-04-24
ps
http://citeseer.ist.psu.edu/14240.html
http://www-mr.wbmt.tudelft.nl/~callafon/n480.ps
en
unrestricted
1996-04-24
CiteSeerPSUset
Filtering and Parametrization issues ...
R. A. De Callafon Filtering and Parametrization issues in Feedback Relevant Identification based on Fractional Model Representations
This report discusses filtering and parametrization issues involved in the usage of
fractional representations in multivariable, approximate and feedback relevant identification
of a possibly unstable plant operating under closed loop conditions. It will
be shown that the access to any stable right coprime factorization of the plant can be
gained by employing the knowledge of the controller and to perform a specific filtering
of the signals present in the closed loop system. Then a linear time invariant model
with a prespecified McMillan degree can be estimated via the identification of a stable
coprime fractional representation wherein a specific class of parametrizations, having
the same McMillan degree, has to be used. Furthermore, it will be shown that an approximate
and feedback relevant estimation of a fixed order linear time invariant model
based on coprime factor identification leads to an additional constraint, which can be
written down explicitly and boils down to a relation ...
The Pennsylvania State University CiteSeer Archives
unknown
1996-04-24
ps
http://citeseer.ist.psu.edu/191913.html
http://www-mr.wbmt.tudelft.nl/~callafon/n478.ps
en
unrestricted
2001-05-07
CiteSeerPSUset
Acyclic and Oriented Chromatic...
Acyclic and Oriented Chromatic Numbers of Graphs
. The oriented chromatic number o (
~
G) of an oriented graph
~
G = (V; A) is the minimum number
of vertices in an oriented graph
~ H for which there exists a homomorphism of
~ G to
~ H . The oriented chromatic
number o (G) of an undirected graph G is the maximum of the oriented chromatic numbers of all the orientations
of G. This paper discusses the relations between the oriented chromatic number and the acyclic chromatic
number and some other parameters of a graph. We shall give a lower bound for o (G) in terms of a (G). An
upper bound for o (G) in terms of a (G) was given by Raspaud and Sopena. We also give an upper bound
for o (G) in terms of the maximum degree of G. We shall show that this upper bound is not far from being
optimal.
Keywords. Oriented chromatic number, Acyclic chromatic number.
1
The Pennsylvania State University CiteSeer Archives
unknown
2001-05-07
1997
ps
http://citeseer.ist.psu.edu/449190.html
http://dept-info.labri.u-bordeaux.fr/~sopena/Papiers/Comprimes/ksz97.ps.gz
en
unrestricted
2001-04-18
CiteSeerPSUset
Colorings and Girth of Oriented...
Colorings and Girth of Oriented Planar Graphs
. Homomorphisms between graphs are studied as a generalization of colorings and of chromatic
number. We investigate here homomorphisms from orientations of undirected planar graphs to graphs (not
necessarily planar) containing as few digons as possible. We relate the existence of such homomorphisms to
girth and it appears that these questions remain interesting even if we insist the girth of G is large, an assumption
which makes the chromatic number easy to compute. In particular we prove that every orientation of any large
girth planar graph is 5-colorable and classify those digraphs on 3, 4 and 5 vertices which color all large girth
oriented planar graphs.
Keywords. Graph homomorphisms, Oriented planar graphs, Girth.
1
The Pennsylvania State University CiteSeer Archives
unknown
2001-04-18
ps
http://citeseer.ist.psu.edu/444059.html
http://dept-info.labri.u-bordeaux.fr/~sopena/Papiers/Comprimes/nrs97.ps.gz
en
unrestricted
2001-04-23
CiteSeerPSUset
The Chromatic Number of Oriented Graphs
The Chromatic Number of Oriented Graphs
. We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of
an antisymmetric directed graph) dened as the minimum order of an oriented graph H such that G admits a
homomorphism to H . We study the chromatic number of oriented k-trees and of oriented graphs with bounded
degree. We show that there exist oriented k-trees with chromatic number at least 2
k+1
1 and that every
oriented k-tree has chromatic number at most (k + 1) 2
k
. For 2-trees and 3-trees we decrease these upper
bounds respectively to 7 and 16 and show that these new bounds are tight. As a particular case, we obtain
that oriented outerplanar graphs have chromatic number at most 7 and that this bound is tight too. We then
show that every oriented graph with maximum degree k has chromatic number at most (2k 1) 2
2k 2
. For
oriented graphs with maximum degree 2 we decrease this bound to 5 and show that this new bound is tight.
For oriented graphs with maximum degree 3 we decrease this bound to 16 and conjecture that there exists no
such connected graph with chromatic number greater than 7.
Keywords. Graph coloring, Graph homomorphism, Oriented coloring.
1
The Pennsylvania State University CiteSeer Archives
unknown
2001-04-23
ps
http://citeseer.ist.psu.edu/453050.html
http://dept-info.labri.u-bordeaux.fr/~sopena/Papiers/Comprimes/s97.ps.gz
en
unrestricted
2001-05-07
CiteSeerPSUset
Acyclic and Oriented Chromatic Numbers...
Acyclic and Oriented Chromatic Numbers of Graphs
. The oriented chromatic number o (
~
G) of an oriented graph
~
G = (V; A) is the minimum number
of vertices in an oriented graph
~ H for which there exists a homomorphism of
~ G to
~ H . The oriented chromatic
number o (G) of an undirected graph G is the maximum of the oriented chromatic numbers of all the orientations
of G. This paper discusses the relations between the oriented chromatic number and the acyclic chromatic
number and some other parameters of a graph. We shall give a lower bound for o (G) in terms of a (G). An
upper bound for o (G) in terms of a (G) was given by Raspaud and Sopena. We also give an upper bound
for o (G) in terms of the maximum degree of G. We shall show that this upper bound is not far from being
optimal.
Keywords. Oriented chromatic number, Acyclic chromatic number.
1
The Pennsylvania State University CiteSeer Archives
unknown
2001-05-07
1997
ps
http://citeseer.ist.psu.edu/449190.html
http://dept-info.labri.u-bordeaux.fr/~sopena/Papiers/Comprimes/ksz97.ps.gz
en
unrestricted
2002-07-19
CiteSeerPSUset
A Survey of Current Paradigms
Bonnie J. Dorr
A.V.. Williams Building; College Park , Maryland 20742
Computer Science Department; University of Maryland
John W. Benoit
7525 Colshire Drive; McLean , Virginia 22102
Artificial Intelligence Center
Mitre Corporation
7525 Colshire Drive; McLean , Virginia 22102
Artificial Intelligence Center
Pamela W. Jordan
901 Cathedral of Learning; Pittsburgh , PA 15260
Intelligent Systems Program; University of Pittsburgh
Bonnie J. Dorr,John W. Benoit,Mitre Corporation,Pamela W. Jordan A Survey of Current Paradigms
This paper is a survey of the current machine translation research
in the US, Europe and Japan. A short history of machine translation
is presented first, followed by an overview of the current research
work. Representative examples of a wide range of different approaches
adopted by machine translation researchers are presented. These are
described in detail along with a discussion of the practicalities of scaling
up these approaches for operational environments. In support of this
discussion, issues in, and techniques for, evaluating machine translation
systems are addressed.
The Pennsylvania State University CiteSeer Archives
unknown
2002-07-19
ps
http://citeseer.ist.psu.edu/555445.html
http://www.umiacs.umd.edu/lamp/pubs/TechReports/LAMP_027/LAMP_027.ps
en
unrestricted
1999-10-29
CiteSeerPSUset
A Matching Technique In Example-Based...
Harris Papageorgiou
Institute for Language and Speech Processing , GREECE
Lambros Cranias
Institute for Language and Speech Processing , GREECE
Stelios Piperidis
Institute for Language and Speech Processing , GREECE
Harris Papageorgiou,Lambros Cranias,Stelios Piperidis A Matching Technique In Example-Based Machine Translation
This paper addresses an important problem
in Example-Based Machine Translation (EBMT),
namely how to measure similarity between a sentence
fragment and a set of stored examples. A new
method is proposed that measures similarity according
to both surface structure and content. A second
contribution is the use of clustering to make retrieval
of the best matching example from the database
more efficient. Results on a large number of test
cases from the CELEX database are presented.
1 INTRODUCTION
EBMT is based on the idea of performing translation
by imitating translation examples of similar sentences
[Nagao 84]. In this type of translation system,
a large amount of bi/multi-lingual translation examples
has been stored in a textual database and input
expressions are rendered in the target language by
retrieving from the database that example which is
most similar to the input.
There are three key issues which pertain to
example-based translation:
ffl establishment of correspondence be...
The Pennsylvania State University CiteSeer Archives
unknown
1999-10-29
ps
http://citeseer.ist.psu.edu/245808.html
http://flp.cs.tu-berlin.de/~stede/Download/ebmt1.ps
en
unrestricted
2001-05-15
CiteSeerPSUset
A Survey of Current Paradigms
Bonnie J. Dorr,John W. Benoit,Pamela W. Jordan A Survey of Current Paradigms
This paper is a survey of the current machine translation research
in the US, Europe and Japan. A short history of machine translation
is presented first, followed by an overview of the current research
work. Representative examples of a wide range of different approaches
adopted by machine translation researchers are presented. These are
described in detail along with a discussion of the practicalities of scaling
up these approaches for operational environments. In support of this
discussion, issues in, and techniques for, evaluating machine translation
systems are addressed.
The Pennsylvania State University CiteSeer Archives
unknown
2001-05-15
ps
http://citeseer.ist.psu.edu/553994.html
http://www.ai.mit.edu/people/jimmylin/papers/Dorr00.ps
en
unrestricted
1998-06-24
CiteSeerPSUset
Augmenting WordNet-like lexical resources ...
Simonetta Montemagni
Via della Faggiola 32 , Pisa , ITALY
Istituto di Linguistica Computazionale , CNR
Vito Pirrelli
Via della Faggiola 32 , Pisa , ITALY
Istituto di Linguistica Computazionale , CNR
Simonetta Montemagni,Vito Pirrelli Augmenting WordNet-like lexical resources with distributional evidence. An application-oriented perspective
The paper deals with the issue of how and to what extent
WordNet-like resources provide the necessary information
for an assessment of semantic similarity which is useful for
practical applications. The general point is made that
taxonomical information should be complemented with
distributional evidence. The claim is substantiated through
experimental data and an illustration of a word sense
disambiguation system (SENSE) capable of using
contextually-relevant semantic similarity.
1. Introduction
Assessment
*
of semantic similarity has proved to be be
essential for a variety of Natural Language Processing
(NLP) tasks, including syntactic disambiguation
(either structural or functional), word sense
disambiguation, selection of appropriate translation
equivalent, assessment of lexical cohesion in texts for
automatic summarisation, query expansion and
document indexing in Information Retrieval.
Typically, the semantic similarity between words
is computed on the basis of taxonomical re...
The Pennsylvania State University CiteSeer Archives
unknown
1998-06-24
ps
http://citeseer.ist.psu.edu/65150.html
http://www.ai.sri.com/~harabagi/coling-acl98/acl_work/simonetta.ps.gz
en
unrestricted
2002-12-11
CiteSeerPSUset
A Matciiing Technique In Example...
Harris Papageorgiou,Lambros Cranias,Stelios Piperidis A Matciiing Technique In Exampl E-Based Maciiine Translation
This paper addresses an important problem in
Example-Based Machine Translation (EBMT), namely
how to measure similarity between a sentence fragment
and a set of stored examples. A new method is
proposed that measures similarity according to both
surthce structure and content. A second contribution is
the use of clustering to make retrieval of the best
matching example from the database more efficient.
Results on a large number of test cases from the
CELEX database are presented.
The Pennsylvania State University CiteSeer Archives
unknown
2002-12-11
pdf
http://citeseer.ist.psu.edu/572728.html
http://acl.ldc.upenn.edu/C/C94/C94-1014.pdf
en
unrestricted
2000-06-16
CiteSeerPSUset
The Effects of Word Order and Segmentation ...
Hozumi Tanaka
2-12-1 Ookayama , Meguro-ku , Tokyo 152-8552 JAPAN
Tokyo Institute of Technology
Timothy Baldwin
2-12-1 Ookayama , Meguro-ku , Tokyo 152-8552 JAPAN
Tokyo Institute of Technology
Hozumi Tanaka,Timothy Baldwin The Effects of Word Order and Segmentation on Translation Retrieval Performance
This research looks at the effects of word order
and segmentation on translation retrieval performance
for an experimental Japanese-English translation
memory system. We implement a number
of both bag-of-words and word order-sensitive
similarity metrics, and test each over characterbased
and word-based indexing. The translation
retrieval performance of each system configuration
is evaluated empirically through the notion of word
edit distance between translation candidate outputs
and the model translation. Our results indicate
that character-based indexing is consistently superior
to word-based indexing, suggesting that segmentation
is an unnecessary luxury in the given domain.
Word order-sensitive approaches are demonstrated
to generally outperform bag-of-words methods, with
source language segment-level edit distance proving
the most effective similarity metric.
1 Introduction
Translation memories (TM's) are a well-established
technology within the human and machine translation
fra...
The Pennsylvania State University CiteSeer Archives
unknown
2000-06-16
ps
http://citeseer.ist.psu.edu/396780.html
http://tanaka-www.cs.titech.ac.jp/%7Etim/papers/coling2000.ps.gz
en
unrestricted
1998-05-07
CiteSeerPSUset
Code-Disjoint Circuits for Parity Codes
Egor S. Sogomonyan
Hendrik Hartje
14415 Potsdam , Germany
1); 1 ) University of Potsdam , Institute of Computer Sciences; Fault Tolerant Computing Group
Michael Gossel
11 78 06 Moscow , Russia
2 ) Institute of Control Sciences; Russian Academy of Sciences
Egor S. Sogomonyan,Hendrik Hartje,Michael Gossel Code-Disjoint Circuits for Parity Codes
In this paper it is shown how a circuit, given as a netlist
of gates, can be transformed into two different
types of code-disjoint circuits. A new method for
a joint design of the functional circuit, the output
parity and the input parity is proposed. Carefully
selected internal nodes of the functional circuit are
utilized to reduce the necessary area overhead for the
design of input and output parities.
1 Introduction
The design of self-testing and self-checking circuits
is of growing interest now. The outputs of the
monitored circuit are elements of an error detecting
code; for instance, a parity code or a Berger
code [4, 5, 9, 10, 12--14, 17]. The encoded outputs of
the self-testing or self-checking circuit are monitored
by a (self-testing) code-checker. Internal faults of the
monitored circuit or the checker can be detected by
this method. To also detect faults at the input lines,
code-disjoint circuits have to be used [13]. Both the
inputs and the outputs of a code-disjoint circu...
The Pennsylvania State University CiteSeer Archives
unknown
1998-05-07
ps
http://citeseer.ist.psu.edu/28490.html
http://www.mpag-inf.uni-potsdam.de/papers/ATS-97.ps.gz
en
unrestricted
2001-07-05
CiteSeerPSUset
Logic Synthesis of Multilevel ...
Edward J. Mccluskey
Nur A. Touba
Edward J. Mccluskey,Nur A. Touba Logic Synthesis of Multilevel Circuits with Concurrent Error Detection
This paper presents a procedure for synthesizing multilevel
circuits with concurrent error detection. All errors caused by single stuckat
faults are detected using a parity-check code. The synthesis procedure
(implemented in Stanford CRC's TOPS synthesis system) fully automates
the design process, and reduces the cost of concurrent error detection
compared with previous methods. An algorithm for selecting a good
parity-check code for encoding the circuit outputs is described. Once
the code has been selected, a new procedure called structure-constrained
logic optimization is used to minimize the area of the circuit as much as
possible while still using a circuit structure that ensures that single stuckat
faults cannot produce undetected errors. It is proven that the resulting
implementation is path fault secure, and when augmented by a checker,
forms a self-checking circuit. The actual layout areas required for selfchecking
implementations of benchmark circuits generated with the
techniques described in this paper are compared with implementations
using Berger codes, single-bit parity, and duplicate-and-compare. Results
indicate that the self-checking multilevel circuits generated with the
procedure described here are significantly more economical.
I.
The Pennsylvania State University CiteSeer Archives
unknown
2001-07-05
pdf
http://citeseer.ist.psu.edu/445938.html
http://www.ece.utexas.edu/~touba/research/tcad97.pdf
en
unrestricted
1998-05-08
CiteSeerPSUset
A New Design Method for Unidirectional...
A New Design Method for Unidirectional Circuits
In this paper, a new method for the design of unidirectional
combinational circuits is proposed. Carefully
selected non-unidirectional gates of the original circuit
are duplicated such that every single gate fault can only
be propagated to the circuit outputs on paths with either
an even or an odd number of inverters. Unlike previous
methods, it is not necessary to localize all the inverters of
the circuit at the primary inputs. The average area overhead
is less than half of the area overhead of other known
methods. All single stuck-at faults are detected by the
method proposed.
1. Introduction
The design of self-checking circuits [1], [2], [3] is
becoming more and more important as the complexity of
VLSI continues to increase. In addition to permanent
faults, transient faults are becoming of greater concern.
Self-checking circuits have the ability to detect both transient
faults and permanent faults.
The combination of methods for on-line error detection
or concurrent checking and t...
The Pennsylvania State University CiteSeer Archives
unknown
1998-05-08
ps
http://citeseer.ist.psu.edu/23344.html
http://www.mpag-inf.uni-potsdam.de/papers/OLTW-96.ps.gz
en
unrestricted
1999-07-19
CiteSeerPSUset
Synthesis of Circuits with Low-Cost Concurrent ...
Debaleena Das
Austin , TX 78712-1084
Computer Engineering Research Center; Department of Electrical and Computer Engineering; University of Texas
Debaleena Das,Nur A. Touba Synthesis of Circuits with Low-Cost Concurrent Error Detection Based on Bose-Lin Codes
This paper presents a procedure for synthesizing sequential machines with concurrent error
detection based on Bose-Lin codes. Bose-Lin codes are an efficient solution for providing concurrent
error detection as they are separable codes and have a fixed number of check bits, independent of the
number of information bits. Furthermore, Bose-Lin code checkers have a simple structure as they are
based on modulo operations. Procedures are described for synthesizing circuits in a way that their
structure ensures that all single-point faults can only cause errors that are detected by a Bose-Lin
code. This paper presents an efficient scheme for concurrent error detection in sequential circuits
with no constraint on the state encoding. Concurrent error detection for both the state bits and the
output bits is based on a Bose-Lin code and their checking is combined such that one checker
suffices. Results indicate low area overhead. The cost of concurrent error detection is reduced
significantly co...
The Pennsylvania State University CiteSeer Archives
unknown
1999-07-19
ps
http://citeseer.ist.psu.edu/254685.html
http://www.ece.utexas.edu/~touba/research/jetta.ps
en
unrestricted
1998-05-07
CiteSeerPSUset
Synthesis of Code-disjoint Combinational...
Egor S. Sogomonyan,Hendrik Hartje,Michael Gossel Synthesis of Code-disjoint Combinational Circuits
In this paper it is shown how a circuit, given as a netlist
of gates, can be transformed into a code-disjoint
circuit. Carefully selected gates of the separately implemented
parity bit are utilized for the optimization
of the necessary area overhead.
1 Introduction
The design of self-testing and self-checking circuits
is of growing interest now. The outputs of the
monitored circuit are elements of an error detecting
code; for instance, a parity code or a Berger
code [4, 6, 9--13, 16]. The encoded outputs of the
self-testing or self-checking circuit are monitored by
a (self-testing) code-checker. Internal faults of the
monitored circuit or the checker can be detected by
this method. To also detect faults at the input lines,
code-disjoint circuits have to be used [12]. Both the
inputs and the outputs of a code-disjoint circuit are
encoded [3]. As long as no error occurs input codewords
are mapped onto output code-words and noncode
inputs are mapped onto non-code outputs by a
code-disjoi...
The Pennsylvania State University CiteSeer Archives
unknown
1998-05-07
ps
http://citeseer.ist.psu.edu/177023.html
http://www.mpag-inf.uni-potsdam.de/papers/ETW-97.1.ps.gz
en
unrestricted
2001-03-05
CiteSeerPSUset
Diversity Techniques for Concurrent ...
Subhasish Mitra
; Gates Building 2A , Room 236; Stanford , California 94305
; 00-7 Center for Reliable Computing; Computer Systems Laboratory; June 2000 Dept . of Electrical Engineering and Computer Science; Stanford University
Subhasish Mitra Diversity Techniques for Concurrent Error Detection
:
This technical report contains the text of Subhasish Mitra's PhD thesis "Diversity
Techniques for Concurrent Error Detection."
Funding:
This research was supported by the Advanced Research Projects Agency under
Contract No. DABT63-97-C-0024.
Copyright 2000 by Subhasish Mitra.
All rights reserved, including the right to reproduce this report, or portions thereof, in any
form.
ii
DIVERSITY TECHNIQUES FOR
CONCURRENT ERROR DETECTION
A DISSERTATION
SUBMITTED TO THE DEPARTMENT OF ELECTRICAL ENGINEERING
AND THE COMMITTEE ON GRADUATE STUDIES
OF STANFORD UNIVERSITY
IN PARTIAL FULFILLMENT OF THE REQUIREMENTS
FOR THE DEGREE OF
DOCTOR OF PHILOSOPHY
By
Subhasish Mitra
May 2000
iii
Copyright by Subhasish Mitra 2000
All Rights Reserved
iv
I certify that I have read this dissertation and that in my opinion it is fully adequate, in
scope and quality, as a dissertation for the degree of Doctor of Philosophy.
_________________________________
Edward J. McCluskey (Principal A...
The Pennsylvania State University CiteSeer Archives
unknown
2001-03-05
pdf
http://citeseer.ist.psu.edu/434301.html
http://www-crc.stanford.edu/crc_papers/CRC-TR-00-7.pdf
en
unrestricted
1999-10-13
CiteSeerPSUset
Design of VHDL based Totally Self-Checking ...
C. Bolchini
D. Sciuto
F. Salice
R. Mont
C. Bolchini,D. Sciuto,F. Salice,R. Mont Design of VHDL based Totally Self-Checking Finite State Machine and Data Path Descriptions
This paper presents a complete methodology to design a Totally Self-Checking sequential architecture based on the generic architecture of FSMD (finite state machine and data path), such as the one deriving from VHDL specifications. The control part of the system is designed to be Self-Checking by adopting a state assignment providing a constant Hamming distance between each present state, next state pair of binary codes. The design of the data path is based on both classical methodologies (e. g., Parity, Berger code) and ad-hoc strategies (e. g., multiplexer cycle) suited for the specific circuit structure. Self-Checking properties and costs are evaluated on a set of benchmark FSMs and on a number of VHDL circuits. Index Terms -- Totally Self-Checking, Finite State Machine and Data path (FSMD), detecting codes, checker circuits, state encoding, VHDL. 1. INTRODUCTION Self-Checking (SC) devices are increasingly becoming a suitable approach to the design of complex systems, to cope wit...
The Pennsylvania State University CiteSeer Archives
unknown
1999-10-13
pdf
http://citeseer.ist.psu.edu/434537.html
ftp://ftp.elet.polimi.it/outgoing/Cristiana.Bolchini/Papers/TransVLSI.pdf
en
unrestricted
1998-03-03
CiteSeerPSUset
Synthesis of Circuits with Low-Cost Concurrent ...
Debaleena Das,Nur A. Touba Synthesis of Circuits with Low-Cost Concurrent Error Detection Based on Bose-Lin Codes
This paper presents a procedure for synthesizing
multilevel circuits with concurrent error detection based
on Bose-Lin codes. Bose-Lin codes are an efficient
solution for providing concurrent error detection as they
are separable codes and have a fixed number of check
bits, independent of the number of information bits.
Furthermore, Bose-Lin code checkers have a simple
structure as they are based on modulo operations.
Procedures are described for synthesizing circuits in a
way that their structure ensures that all single-point
faults can only cause errors that are detected by a BoseLin
code. This paper also presents an efficient scheme
for concurrent error detection in sequential circuits.
Both the state bits and the output bits are encoded with a
Bose-Lin code and their checking is combined such that
one checker suffices. Results indicate low area
overhead. The cost of concurrent error detection is
reduced significantly compared to other methods.
1. Introduction
In applications wher...
The Pennsylvania State University CiteSeer Archives
unknown
1998-03-03
ps
http://citeseer.ist.psu.edu/257818.html
http://www.ece.utexas.edu/~touba/research/bl-vts98.ps
en
unrestricted
1999-02-17
CiteSeerPSUset
Weight-Based Codes and Their Application ...
Debaleena Das,Nur A. Touba Weight-Based Codes and Their Application to Concurrent Error Detection of Multilevel Circuits
This paper proposes a new class of codes termed
"weight-based codes" where each output bit is assigned
a weight and the check bits represent the sum of the
weights of the output bits which have value `1'. A
Berger code is a special member of this proposed class
of codes where each output bit is assigned a weight of
one. This paper describes the application of these codes
for the efficient on-line error detection of arbitrary
multilevel circuits. The overall probability of detecting
any number of erroneous bits at the output caused by a
single internal fault is shown to be higher for weightbased
codes than standard error detecting codes.
Further, a very efficient design exists for the checker.
The checker is area and speed efficient, has low power
consumption, and can be tested by a small set of
incoming code words. There is always a tradeoff
between the fault detection capability and area overhead
requirement of an error detecting code. Weight-based
codes present a controlled way of in...
The Pennsylvania State University CiteSeer Archives
unknown
1999-02-17
ps
http://citeseer.ist.psu.edu/250154.html
http://www.ece.utexas.edu/~touba/research/code-vts99.ps
en
unrestricted