bluuebunny/crossref_metadata_2025 huggingface dataset:
TRIANGULATING POLYGONS WITHOUT LARGE ANGLES
Authors: BERN MARSHALL , DOBKIN DAVID , EPPSTEIN DAVID
Published: November 2004

We show how to triangulate polygonal regions—adding extra vertices as necessary— with triangles of guaranteed quality. Using only O(n) triangles, we can guarantee that the smallest height (shortest dimension) of a triangle in a triangulation of an n-vertex polygon (with holes) is a constant fraction of the largest possible. Using O(n log n) triangles for simple polygons or O(n3/2) triangles for polygons with holes, we can guarantee that the largest angle is no greater than 150°. We can add the guarantee on smallest height to these no-large-angle results, without increasing the asymptotic complexity of the triangulation. Finally we give a nonobtuse triangulation algorithm for convex polygons that uses O(n1.85) triangles.
NUMERICAL STABILITY OF ALGORITHMS FOR 2D DELAUNAY TRIANGULATIONS
Authors: FORTUNE STEVEN
Published: November 2004

We consider the correctness of 2-d Delaunay triangulation algorithms implemented using floating-point arithmetic. The α-pseudocircle through points a, b, c consists of three circular arcs connecting ab, bc, and ac, each arc inside the circumcircle of a, b, c and forming angle α with the circumcircle; a triangulation is α-empty if the α-pseudocircle through the vertices of each triangle is empty. We show that a simple Delaunay triangulation algorithm—the flipping algorithm—can be implemented to produce O(n∈)-empty triangulations, where n is the number of point sites and ∈ is the relative error of floating-point arithmetic; its worst-case running time is O(n2). We also discuss floating-point implementation of other 2-d Delaunay triangulation algorithms.
COMPUTING THE ALL-PAIRS LONGEST CHAINS IN THE PLANE
Authors: ATALLAH MIKHAIL J. , CHEN DANNY Z.
Published: November 2004

Many problems on sequences and on special kinds of graphs involve the computation of longest chains passing points in the plane. Given a set S of n points in the plane, we consider the problem of computing the matrix of longest chain lengths between all pairs of points in S, and the matrix of “parent” pointers that describes the n longest chain trees. We present a simple sequential algorithm for computing these matrices. Our algorithm runs in O(n2) time, and hence is optimal. We also present a rather involved parallel algorithm that computes these matrices in O((log n)2) time using O(n2/log n) processors in the CREW PRAM model. These matrices enable us to report, in O(1) time, the length of a longest chain between any two points in S by using one processor, and the actual chain by using k processors, where k is the number of points of S on that chain. The space complexity of the algorithms is O(n2).
SEARCHING FOR A MOBILE INTRUDER IN A CORRIDOR —THE OPEN EDGE VARIANT OF THE POLYGON SEARCH PROBLEM
Authors: CRASS DAVID , SUZUKI ICHIRO , YAMASHITA MASAFUMI
Published: November 2004

The polygon search problem is the problem of searching for mobile intruders in a simple polygon by a single mobile searcher having various degrees of visibility. This paper considers the “open edge” variant of the problem in which the given polygon P must be searched without allowing undetected intruders to reach a given edge u, under an additional assumption that any number of intruders can leave and enter P through another edge v at any time. One may view P as representing a corridor with two open exits u and v, and the task of the searcher is to force all the intruders out of P through v (but not u). We present a simple necessary condition for a polygon to be searchable in this manner by the searcher having a light bulb, and then show that the same condition is sufficient for the polygon to be searchable by the searcher having two flashlights. The time complexity of generating a search schedule is also discussed.
COMPUTING MINKOWSKI SUMS OF PLANE CURVES
Authors: KAUL ANIL , FAROUKI RIDA T.
Published: November 2004

The Minkowski sum of two plane curves can be regarded as the area generated by sweeping one curve along the other. The boundary of the Minkowski sum consists of translated portions of the given curves and/or portions of a more complicated curve, the “envelope” of translates of the swept curve. We show that the Minkowski-sum boundary is describable as an algebraic curve (or subset thereof) when the given curves are algebraic, and illustrate the computation of its implicit equation. However, such equations are typically of high degree and do not offer a practical basis for tracing the boundary. For the case of polynomial parametric curves, we formulate a simple numerical procedure to address the latter problem, based on constructing the Gauss maps of the given curves and using them to identifying “corresponding” curve segments that are to be summed. This yields a set of discretely-sampled arcs that constitutes a superset of the Minkowski-sum boundary, and can be regarded as a planar graph. To extract the true boundary, we present a method for identifying and “trimming” away extraneous arcs by systematically traversing this graph.
ON THE DECIDABILITY OF THE MEMBERSHIP PROBLEM OF THE PSEUDOVARIETY J∨B
Authors: ZEITOUN MARC
Published: November 2004

The aim of this article is to prove that the pseudovariety generated by J∪B, that is to say, the join of the pseudovariety of [Formula: see text]-trivial semigroups and of the pseudovariety of idempotents semigroups, is decidable. The techniques used were developed by Almeida and are based on the study of the topological semigroup of implicit operations.
MINIMAL AUTOMORPHIC POSETS AND THE PROJECTION PROPERTY
Authors: LAROSE BENOIT
Published: November 2004

We present some results concerning the projection property for finite ordered sets. We show that sums of non-trivial ramified ordered sets over a connected poset of at least two elements are projective. We construct a family of minimal automorphic posets of reach 2 and length 2 and show they are projective.
REWRITING A SEMIGROUP PRESENTATION
Authors: CAMPBELL C.M. , ROBERTSON E.F. , RUŠKUC N. , THOMAS R.M.
Published: November 2004

Let [Formula: see text] be a finitely presented semigroup having a minimal left ideal L and a minimal right ideal R. The main result gives a presentation for the group R∩L. It is obtained by rewriting the relations of [Formula: see text], using the actions of [Formula: see text] on its minimal left and minimal right ideals. This allows the structure of the minimal two-sided ideal of [Formula: see text] to be described explicitly in terms of a Rees matrix semigroup. These results are applied to the Fibonacci semigroups, proving the conjecture that S(r, n, k) is infinite if g.c.d.(n, k)>1 and g.c.d.(n, r+k−1)>1. Two enumeration procedures, related to rewriting the presentation of [Formula: see text] into a presentation for R∩L, are described. The first enumerates the minimal left and minimal right ideals of [Formula: see text], and gives the actions of [Formula: see text] on these ideals. The second enumerates the idempotents of the minimal two-sided ideal of [Formula: see text].
COMMUTATORS IN FREE PRODUCTS
Authors: CLIFFORD ANDREW
Published: November 2004

Topological methods are used to show that for certain subgroups S of a free product F, if w∈S is a commutator in F, then w is a commutator in S.
THE FUNDAMENTAL GROUPS OF CLOSED ORIENTABLE 3-MANIFOLDS ADMITTING COLORED TRIANGULATIONS WITH LESS THAN 30 TETRAHEDRA
Authors: LINS SÓSTENES , SIDKI SAID
Published: November 2004

For n even positive integer let [Formula: see text] (gem manifold) be the class of closed orientable 3-manifolds which can be formed by pasting together a collection of at most n tetrahedra which have colors 0, 1, 2, 3 assigned to the vertices so that the pasting obeys the coloring. We provide a thorough analysis of the fundamental groups of [Formula: see text].
RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS
Authors: GORALČÍK PAVEL , KOUBEK VÁCLAV
Published: November 2004

Let (X, F) be a pair consisting of a finite set X and a set F of transformations of X, and, let  and F(l) denote, respectively, the semigroup generated by F and the part of  consisting of the transformations determined by a generator sequence of length no more than a given integer l. We show the following:

• The problem whether or not, for a given pair (X, F) and a given integer r, there is an idempotent transformation of rank r in  is PSPACE-complete.

• For each fixed r≥1, it is decidable in a polynomial time, for a given pair (X, F), whether or not  contains an idempotent transformation of rank r, and, if yes then a generator sequence of polynomial length composing to an idempotent transformation of rank r can be obtained in a polynomial time.

• For each fixed r≥1, the problem whether or not, for a given (X, F) and l, there is an idempotent transformation of rank r in F(l) is NP-complete.

• For each fixed r≥2, to decide, for a given (X, F), whether or not  contains a transformation of rank r is NP-hard.
EXTENSIONS OF REGULAR ORTHOGROUPS BY INVERSE SEMIGROUPS
Authors: BILLHARDT BERND
Published: November 2004

Let V be a variety of regular orthogroups, i.e. completely regular orthodox semigroups whose band of idempotents is regular. Let S be an orthodox semigroup which is a (normal) extension of an orthogroup K from V by an inverse semigroup G, that is, there is a congruence ρ on S such that the semigroup ker ρ of all idempotent related elements of S is isomorphic to K and S/ρ≅G. It is shown that S can be embedded into an orthodox subsemigroup T of a double semidirect product A**G where A belongs to V. Moreover T itself can be chosen to be an extension of a member from V by G. If in addition ρ is a group congruence we obtain a recent result due to M.B. Szendrei [16] which says that each orthodox semigroup which is an extension of a regular orthogroup K by a group G can be embedded into a semidirect product of an orthogroup K′ by G where K′ belongs to the variety of orthogroups generated by K.
SOME NON-FINITELY BASED VARIETIES OF GROUPS AND GROUP REPRESENTATIONS
Authors: GUPTA C.K. , KRASIL’NIKOV A.N.
Published: November 2004

The following results are established: (i) There exists a subvariety of the variety of centre-by-abelian -by- (nilpotent of class 2) groups which is not finitely based; (ii) There exists a variety of group representations (over a field of characteristic 2) which satisfies a multilinear polynomial identity but without any finite basis for its identities: (iii) Over fields of characteristic 2, a product of two Specht varieties of group representations need not be Specht.
CARTAN SUBMONOIDS OF ALGEBRAIC MONOIDS
Authors: HUANG WENXUE
Published: November 2004

Let M be an irreducible linear algebraic monoid defined over an algebraically closed field K with idempotent set E(M), T a maximal torus of the unit group G of M. We call CM(T)c a Cartan submonoid of M. The following are proved: (1) If M is reductive with zero or completely regular, then CM(T) is irreducible and regular and [Formula: see text]; (2) If M is regular, then M is solvable iff NM(CM(T))=CM(T), in which case, CM(T) is irreducible and regular; (3) If M is regular, then [Formula: see text].
A QUASI-AFFINE REPRESENTATION
Authors: KEARNES KEITH A.
Published: November 2004

We describe a quasi-affine representation for algebras having a binary central term.
FACTORIZATION OF THE CONVECTION-DIFFUSION OPERATOR AND THE SCHWARZ ALGORITHM
Authors: NATAF F. , ROGIER F.
Published: November 2004

In the original Schwarz algorithm, Dirichlet boundary conditions are used as interface conditions. We consider the use of the operators arising from the factorization of the convection-diffusion operator as transmission conditions. The rate of convergence is then significantly higher. Theoretical results are proven and numerical tests are shown.
ON NECESSARY AND SUFFICIENT CONDITIONS FOR TURBULENT SECONDARY FLOWS IN A STRAIGHT TUBE
Authors: HUANG YU-NING , RAJAGOPAL K.R.
Published: November 2004

In this paper, we derive necessary and sufficient conditions for the fully-developed turbulent secondary flow of a Newtonian fluid in a straight tube, under the influence of a conservative body force. Under special conditions, we show that in the absence of a body force, we can obtain a sufficient condition for turbulent secondary flow in terms of the transverse normal stress differences associated with the Reynolds stress and the transverse shear component of the Reynolds stress.
AN EXPLICIT HIGH ORDER PREDICTOR-CORRECTOR METHOD FOR PERIODIC INITIAL VALUE PROBLEMS
Authors: SIMOS T.E.
Published: November 2004

An explicit Runge-Kutta type method is developed here. This method has an algebraic order six, a large interval of periodicity and a phase-lag of order eight. It is much more efficient than other well known methods when applying to an orbit equation.
OPTIMAL CONTROL OF A CONVECTIVE-DIFFUSIVE FLUID PROBLEM
Authors: LENHART SUZANNE
Published: November 2004

We consider optimal control of a parabolic differential equation, modeling one-dimensional fluid flow through a soil-packed tube in which a contaminant is initially distributed. A fluid is pumped through the tube to remove the contaminant. The convective velocity due to the fluid pumping is the nonlinear control action. The goal is to minimize a performance criterion which is a combination of the total contaminant at the final time and the cost of the control. The optimal control is characterized by an optimality system.
NUMERICAL ANALYSIS OF THE FINITE ELEMENT METHOD APPLIED TO THE BOLTZMANN-POISSON SYSTEM
Authors: SHUTYAEV V. , TRUFANOV O.
Published: November 2004

This paper is concerned with the numerical analysis of the mathematical model for a semiconductor device with the use of the Boltzmann equation. A mixed initial-boundary value problem for nonstationary Boltzmann-Poisson system in the case of one spatial variable is considered. A numerical algorithm for solving this problem is constructed and justified. The algorithm is based on an iterative process and the finite element method. A numerical example is presented.
STREAMFUNCTION COORDINATE FORMULATION FOR ONE-DIMENSIONAL UNSTEADY FLOW
Authors: AN C.-F. , BARRON R.M. , ZHANG S.
Published: November 2004

In this paper, the streamfunction-as-a-coordinate concept has been extended to 1-D unsteady flow. The governing equation in streamfunction coordinates in this case is a second order nonlinear hyperbolic partial differential equation or a wave equation with variable propagation speed for the Cartesian coordinate x=x(ψ, τ) where ψ is streamfunction and τ is time. The equation has been solved numerically by the leapfrog scheme. A piston-driven expansion wave and a density disturbance propagation have been successfully simulated and the agreement between the present method and exact solution is excellent. The streamfunction coordinate formulation for 1-D unsteady flow is particularly advantageous due to the fact that the Jacobian is always a positive finite quantity so that there is no singularity in the transformation. An additional benefit of the streamfunction formulation for 1-D unsteady flow is the ability to easily draw particle path lines.
RELAXATION TIME APPROXIMATION FOR ELECTRON-PHONON INTERACTION IN SEMICONDUCTORS
Authors: MARKOWICH PETER A. , SCHMEISER CHRISTIAN
Published: November 2004

A Boltzmann equation for semiconductors is considered. Physical assumptions include the parabolic band approximation and a new relaxation time model for electron-phonon interaction. Thermal equilibrium distributions for this scattering mechanism are products of Maxwellian distributions with periodic functions of the energy, where the period is the energy of a phonon. The hydrodynamic limit is considered and a drift-diffusion model is derived by formal asymptotic methods.
THE REGULARITY OF SOLUTIONS FOR THE CURL BOUNDARY PROBLEMS AND GINZBURG-LANDAU SUPERCONDUCTIVITY MODEL
Authors: LIANG JIN
Published: November 2004

In this paper, we discuss the regularity of solutions for curl boundary elliptic and parabolic problems and related Ginzburg-Landau superconductivity models. The solutions are smooth up to C∞ if the boundary and the given data are smooth enough.
COMPLETENESS OF ROOT FUNCTIONS AND ELEMENTARY SOLUTIONS OF THE THERMOELASTICITY SYSTEM
Authors: YAKUBOV YAKOV
Published: November 2004

In this paper we prove the completeness of the root functions (eigenfunctions and associated functions) of an elliptic system (in the sense of Douglis-Nirenberg) corresponding to the thermoelasticity system with the Dirichlet boundary value condition. The problem is considered in a domain with a non-smooth boundary. Then an initial boundary value problem corresponding to the thermoelasticity system with the Dirichlet boundary value condition is considered. We find sufficient conditions that guarantee an approximation of a solution to the initial boundary value problem by linear combinations of some “elementary solutions” to the thermoelasticity system.
A CHANNEL NETWORK MODEL FOR CHEMICAL MIGRATION IN SUBSURFACE MEDIA
Authors: EDWARDS MARK S. , GRINDROD PETER
Published: November 2004

We consider the migration of chemical species through saturated heterogeneous media, where the scale of the flow path geometry is large enough to invalidate a Fickian based, representative elementary volumes, approach to dispersal. Channel network models combine the effects of channeling over small spatial scales with network mixing which gives rise to an equivalent dispersion effect over large spatial scales. We extend equations and solutions given previously for ideal nonabsorbing tracers, to include the retardation of chemically active species. The primary aim is to derive explicit solutions for future calibration purposes, and illustrate scale dependent dispersive behavior with and without chemical absorption processes. In this paper we develop a twin channel model allowing for various specification of the retardation process. This allows the retardation to be either positively or negatively correlated with pathway apertures (which are in turn related directly to flow rates of the respective channels). We show that if absorption is controlled by specific surface area, then a scaling argument infers that highly transmissive paths are also less retarding. We illustrate the model’s applicability to such cases. We shall discuss the scale dependence of calculated (observed) equivalent dispersivities obtained by analyzing the moments of breakthrough curves at various distances. For a range of parameter values we exhibit scaling behavior similar to that observed in the field and laboratory. This does not necessarily imply any validity to the approach: it is a direct consequence of deferring the network — mixing effect to large length scales. An important point of consideration is that wherever conceptual model choices must be made, in modeling natural processes such as chemical migration, there is a possibility of biasing calculations by sole reliance on a particular approach. Channel network models marry channeling models and classical Fickian models. Thus in calibrating a model such as the Twin Channel model from given experimental behavior, we can immediately estimate over which scales channeling or Fickian dispersive effects are likely to be dominant.
SYMMETRY-BREAKING BIFURCATIONS IN STOPPELLI’S PROBLEM FOR PSEUDO-RIGID BODIES
Authors: PIERCE JOHN F.
Published: November 2004

The work examines what changes can occur to the orbit of trivially equilibrating configurations for a pseudo-rigid body possessing a natural state when perturbing loads are applied. The question is analyzed by formulating it as a problem of bifurcation on a group orbit to which the theory of singularities applies. The analysis indicates how alterations of the orbit depend upon features of the perturbing load, and of the material composing the body.
STATIONARY SOLUTIONS TO A QUASI-NEWTONIAN FLOW WITH VISCOUS HEATING
Authors: BARANGER JACQUES , MIKELIĆ ANDRO
Published: November 2004

System of equations describing the stationary flow of a quasi-Newtonian fluid, with temperature-dependent viscosity and with a viscous heating, is considered. Existence of at least one appropriate weak solution is proved, i.e. we get existence of at least one velocity field having finite energy and existence of a non-negative temperature field. Its regularity is a consequence of the L1-forcing term generated by the viscous heating.
KINEMATICS AND THEORY OF FORCES FOR NONMATERIAL INTERFACES
Authors: SEGEV R. , FRIED E.
Published: November 2004

We present a framework for the study of bodies that contains evolving nonmaterial interfaces. Although analogs of material points and sub-bodies do not exist for such interfaces, we are able to construct a kinematic structure that allows the definition of an interfacial configuration. Equipping the collection of all such configurations, the interfacial configuration space, with the structure of an infinite-dimensional manifold leads to the definition of generalized velocities and forces as elements of the tangent and cotangent bundles of that space. A representation theorem then yields a non-classical force system that arises in recent continuum theories for the study of coherent phase transitions. Associating the underlying body with a particular reference configuration, we find, further, that the elements of that force system are subject to a balance that is also imposed in such theories.
ASYMPTOTIC EQUIVALENCE OF A REACTION-DIFFUSION SYSTEM TO THE CORRESPONDING SYSTEM OF ORDINARY DIFFERENTIAL EQUATIONS
Authors: HOSHINO HIROKI , KAWASHIMA SHUICHI
Published: November 2004

Large time behavior of the solution to some simple reaction-diffusion system is studied. It is proved that the solution behaves like the solution to the corresponding system of ordinary differential equations as time goes to infinity. The proof is based on an energy method combined with the Lp−Lqestimate for the associated semigroup.
ASYMPTOTIC ANALYSIS OF A MODEL KINETIC EQUATION
Authors: MIKA JANUSZ R. , BANASIAK JACEK
Published: November 2004

For a simple model of a linear kinetic equation the exact solution is expanded in terms of a small parameter whose presence makes the equation, singularly perturbed. Various asymptotic expansion methods are analyzed and it is shown that the compressed method, which is related to the Chapman-Enskog asymptotic procedure, is the most accurate. This holds when the technique of time rescaling is applied to overcome the difficulties with the application of the standard asymptotic procedure.
BOUNDARY INTEGRAL FORMULATION FOR THE COLLAPSE OF AN INITIALLY SPHERICAL VAPOR CAVITY UNDER THE EFFECT OF THE CURVATURE
Authors: PIACENTINI A.
Published: November 2004

The effect of the curvature is usually neglected in the mathematical models of bubble collapse. For bubbles of sufficiently small radius such effect becomes of relevant interest. A linear boundary element method (B.E.M.) with a cubic spline approximation of the domain that takes the surface tension into account is presented.
PRECONDITIONERS FOR THE MORTAR METHOD BASED ON LOCAL APPROXIMATIONS OF THE STEKLOV-POINCARÉ OPERATOR
Authors: ACHDOU YVES , NATAF FREDERIC
Published: November 2004

Many implicit Navier-Stokes solvers involve the discretization of an elliptic partial differential equation of the type −Δu+ηu=f, where η is a large positive parameter. The discretization studied here is the mortar finite element method, a domain decomposition method allowing nonmatching meshes at subdomains interfaces. Two kinds of improvements are proposed here in order to reduce the condition number of the corresponding linear systems: the first one lies on building preconditioners by approximating Steklov-Poincaré operators on subdomains boundaries by second-order partial differential operators; the second one consists in making a nonstandard choice of jump operators at subdomains interfaces. Both ideas are tested numerically.
ON A SYSTEM OF SEMILINEAR ELLIPTIC EQUATIONS ARISING IN PHYSICAL OCEANOGRAPHY
Authors: CHEN SENHUEI E.
Published: November 2004

In this paper we study a mathematical model which arises in thermocline theory in physical oceanography. The thermocline theory is to explain the phenomenon of the strong, vertical density gradient in a relatively shallow layer of water where the transition occurs from the ocean’s surface temperature to the colder, more uniform waters of the abyss. The governing equations used here are carefully suggested by physical oceanographers. We establish the existence of solutions by a modification of Banach fixed point theorem subject to the boundary conditions which reflect physical situations.
THE TRACE THEOREMS IN ANISOTROPIC SOBOLEV SPACES AND THEIR APPLICATIONS TO THE CHARACTERISTIC INITIAL BOUNDARY VALUE PROBLEM FOR SYMMETRIC HYPERBOLIC SYSTEMS
Authors: SHIZUTA YASUSHI , YABUTA KÔZÔ
Published: November 2004

Anisotropic Sobolev spaces are introduced in order to study the initial boundary value problem for first-order symmetric hyperbolic systems with characteristic boundary of constant multiplicity. A trace theorem is given and used for showing the necessity of the compatibility condition for the existence of solution that lies in the anisotroropic Sobolev space.
CONSTRUCTING PARTIAL AND COMPLETE INTELLIGENT ANSWERS FOR RECURSIVE QUERIES
Authors: ZHANG XUBO , OZSOYOGLU Z. MERAL
Published: November 2004

In this paper we study the issue of providing intelligent answers to recursive queries initially proposed in [Imie88]. In contrast to conventional query answers, which are sets of tuples, intelligent answers are rules describing the characteristics of the results. This way, an intelligent answer facilitates users to better capture the meaning of the query.

To this aim, we first extend the notion of intelligent answers by allowing them to be partial (or incomplete). Complete and partial intelligent answers are both useful, in that they provide (possibly partial) characterizations of queries. We will show that complete intelligent answers also give a more efficient way to evaluate queries. For constructing intelligent answers, we propose a general approach that enables us to combine several cases studied in [Imie88].

Moreover, we will show that semantic constraints can be systematically utilized to provide complete intelligent answers to a wider range of queries. We consider two commonly used classes of semantic constraints called implication and referential constraints, and prove that the completeness of intelligent answers with respect to semantic constraints can be reduced to the semantics-based query containment problem. Finally, a necessary and sufficient condition is given to solve this containment problem.
A KNOWLEDGE-BASED SELECTION MECHANISM FOR STRATEGIC CONTROL WITH APPLICATION IN DESIGN, DIAGNOSIS AND PLANNING
Authors: PUNCH WILLIAM F. , GOEL ASHOK K. , BROWN DAVID C.
Published: November 2004

This paper describes a generic, knowledge-based mechanism for selecting among a fixed set of alternatives. The mechanism, termed sponsor-selector has been used as a control mechanism in a number of different knowledge-based systems including problem-solver integration applications in routine design, diagnostic problem-solving, and navigational planning. For design, the DSPL language uses sponsor-selectors to select between alternate, fixed plans to determine the best approach for the design of an artifact. For diagnosis, the Peirce and TIPS system used sponsor-selectors as the overall control mechanism, determining which problem-solver, out of a group of problem-solving agents, to select under particular problem solving conditions. For navigation planning, the Router system used the sponsor-selector mechanism and the TIPS architecture to select between alternate problem-solving strategies. problem-solving approaches. We describe in this paper the general architecture of the sponsor-selector mechanism and how this mechanism was used in the 4 described systems, along with some performance measures and results.
ATTRIBUTE GRAMMAR BASED MODELING OF CONCURRENT CONSTRAINT LOGIC PROGRAMMING
Authors: VOLIOTIS C. , SGOUROS N.M. , PAPAKONSTANTINOU G.
Published: November 2004

The development of more powerful Concurrent Constraint Logic Programming (CCLP) languages depends largely on the development of environments that facilitate the specification and integration of constraints in the semantics of a logic program and automatically extract the inherent parallelism of Logic Programming. This paper presents a novel method for automating the parallel AND/OR execution of CCLP applications. This method consists of two stages. The first stage translates a logic program into an equivalent Attribute Grammar providing a common language in which the specifications of constraints and the semantics of a logic program can be expressed. The second stage evaluates this Attribute Grammar using MPAGE, a Multipass Parallel Attribute Grammar Evaluation algorithm. Support for the processing of constraints in the logic program is provided with the creation of a dependency graph between the variables of a logic rule during the first stage. Using this dependency graph MPAGE delays, if necessary, the evaluation of variables in a constraint until they become bound at some later point in processing. As a result our method supports rule representations in CLP languages with no restrictions on the ordering of subgoals. Furthermore, during execution MPAGE allows single rules in a CLP program to deal with multiple assignments of bindings, thus generating a minimal number of processes. Finally, this method is independent from the underlying hardware and its memory organization, therefore it can be implemented on both shared and distributed memory systems.
Intersecting Braids and Intersecting Knot Theory
Authors: Armand-Ugon Daniel , Gambini Rodolfo , Mora Pablo
Published: November 2004

An extension of the Artin Braid Group is considered, with the introduction of new operatores that generate double and triple intersections. The extended Alexander theorem, relating intersecting closed braids and intersecting knots is proved for double and triple intersections, and a counter example is given for the case of quadruple intersections. Intersecting knot invariants are also constructed via Markov traces defined on the intersecting braid algebra representations, and the extended Turaev representation is discussed as an example.
ON THE ARITHMETIC 2-BRIDGE KNOTS AND LINK ORBIFOLDS AND A NEW KNOT INVARIANT
Authors: HILDEN HUGH M. , LOZANO MARIA TERESA , MONTESINOS-AMILIBIA JOSE MARIA
Published: November 2004

Let (p/q, n) denote the orbifold with singular set the two bridge knot or link p/q and isotropy group cyclic of orden n. An algebraic curve [Formula: see text] (set of zeroes of a polynomial r(x, z)) is associated to p/q parametrizing the representations of [Formula: see text] in PSL [Formula: see text]. The coordinates x, z, are trace(A2)=x, trace(AB)=z where A and B[Formula: see text] are the images of canonical generators a, b of [Formula: see text]. Let (xn, zn) be the point of [Formula: see text] corresponding to the hyperbolic orbifold (p/q, n). We prove the following result: The (orbifold) fundamental group of (p/q, n) is arithmetic if and only if the field Q(xn, zn) has exactly one complex place and ϕ(xn)<ϕ(zn)<2 for every real embedding [Formula: see text].

Consider the angle α for which the cone-manifold (p/q, α) is euclidean. We prove that 2cosα is an algebraic number. Its minimal polynomial (called the h-polynomial) is then a knot invariant. We indicate how to generalize this h-polynomial invariant for any hyperbolic knot.

Finally, we compute h-polynomials and arithmeticity of (p/q, n) with p≦40, and (p/q, n) with p≦99q2≡1 mod p. We finish the paper with some open problems.
Representations of Artin’s braid groups and linking numbers of periodic orbits
Authors: Guaschi John
Published: November 2004

Let P be a periodic orbit of period n≥3 of an orientation-preserving homeomorphism f of the 2-disc. Let q be the least integer greater than or equal to n/2−1. Then f admits a periodic orbit Q of period less than or equal to q such that the linking number of P about Q is non-zero. This answers a question of Franks in the affirmative in the case that P has small period. We also derive a result regarding matrix representations of Artin’s braid groups. Finally a lower bound for the topological entropy of a braid in terms of the trace of its Burau matrix is found.
UNKNOTTING ORIENTABLE SURFACES IN THE 4-SPHERE
Authors: HILLMAN JONATHAN A. , KAWAUCHI AKIO
Published: November 2004

We show that a topologically locally flat embedding of a closed orientable surface in the 4-sphere is isotopic to one whose image lies in the equatorial 3-sphere if and only if its exterior has an infinite cyclic fundamental group.
The Absolute Value of The Chern-Simons-Witten Invariants of Lens Spaces
Authors: YAMADA SHUJI
Published: November 2004

An explicit formula for the absolute value of the Witten invariants is derived. We discuss the relation between homotopy equivalence and the absolute value of Witten invariants for lens spaces. We also give examples of arbitrarily finitely many lens spaces which have the same Witten invariants for any level r.
A Revised Version of P. L. PROPER KNOT EQUIVALENCE CLASSES ARE GENERATED BY LOCALLY FLAT ISOTOPIES (Vol. 3, No. 4 (December 94), pp. 497–509)
Authors: NANYES OLLIE
Published: November 2004

A p. 1. proper knot is a proper p. 1. embedding of the real line into a p. 1. open 3-manifold. Two p. 1. proper knots are said to be equivalent if there is a p. 1. proper isotopy (possibly non-ambient) connecting them. A priori such an isotopy need not be locally flat: for example a local knot in the range could be shrunk to a point within a 3-cell. In this paper we show that, in essence, this is the only type of non-locally flat phenomenon. We show that such a local knot can always be “combed to infinity”. Thus if two p. 1. proper knots are connected by a p. 1. proper isotopy then the connecting isotopy can be modified to be a locally flat p. 1. proper isotopy. Hence, in proper knot theory, the smooth category and the p. 1. category are similar.
RIBBON KNOTS AND INVARIANTS OF THETA-CURVES
Authors: MARUMOTO YOSHIHIKO
Published: November 2004

We define invariants of higher dimensional theta-curves, and give a characterization of a trivial curve in the case of the classical dimension. We introduce a ribbon presentation of a knot and equivalence in ribbon presentations. Then a ribbon presentation induces a theta-curve, and invariants of theta-curves give those of ribbon presentations. Using the invariants, we can distinguish ribbon presentations of a knot.
THE (2, ∞)-SKEIN MODULE OF THE COMPLEMENT OF A (2, 2p+1) TORUS KNOT
Authors: BULLOCK DOUG
Published: November 2004

In this paper we extend the list of three manifolds for which the (2, ∞)-skein module is known by giving the first explicit calculations for non-trivial knot exteriors. We show that for the complement of a (2, 2p+1) torus knot the module is free with a very simple basis. As a consequence, we obtain a family of polynomial invariants for links in these manifolds. The invariants are analogous to the Jones polynomial for links in S3.
CONSISTENCY OF JUDGEMENT MATRIX AND FUZZY WEIGHTS IN FUZZY ANALYTIC HIERARCHY PROCESS
Authors: WANG XUZHU , KERRE E.E. , RUAN D.
Published: November 2004

In this paper we introduce a definition of consistency of the judgement matrix in the fuzzy Analytic Hierarchy Process (AHP) and give a general expression of all fuzzy weights under the condition of consistency. Finally, based on our discussion, the geometric average method is suggested for fuzzy weights calculation in the practical decision-making situation.
REFERENCE CLASSES AND MULTIPLE INHERITANCES
Authors: WANG PEI
Published: November 2004

The reference class problem in probability theory and the multiple inheritances (extensions) problem in non-monotonic logics are special cases of conflicting beliefs. One popular solution accepted in the two domains is the specificity principle. By analyzing an example, several factors beyond specificity are found to be relevant to the priority of a reference class. A new approach, Non-Axiomatic Reasoning System (NARS), is discussed, where these factors are all taken into account. It is argued that the solution provided by NARS is better than the solutions provided by probability theory and non-monotonic logics.
FURTHER RESULTS IN QUALITATIVE UNCERTAINTY
Authors: PARSONS SIMON
Published: November 2004

This paper extends previous work on propagating qualitative uncertainty in networks in which a general approach to qualitative propagation was discussed. The work presented here includes results that make it possible to perform evidential and intercausal reasoning, in addition to the predictive reasoning already covered, in networks quantified with probability, possibility and Dempster-Shafer belief values. The use of these forms of reasoning, which include the phenomenon of “explaining away”, is illustrated with the use of a medical example.
HYBRID LOCATION-CONTENT ADDRESSABLE MEMORY WITH ITS APPLICATION TO CHARACTER RECOGNITION
Authors: KOH S.B. , KIM J.H. , WANG B.H.
Published: November 2004

This paper reviews the Hybrid Location-Content Addressable Memories (HyLCAMs) and applies them to the printed character recognition problem in order to illustrate their performance in real world problems. Three indirect code generation methods which are the key of the HyLCAM encoding is described to determine a set of proper intermediate states that are linearly separable with inputs. Rejection mechanisms based on code mismatch and rejection region of activation functions are introduced. Computer simulations are performed in order to compare generalization abilities and performance on the rejection mechanism of the HyLCAM models with those of the multilayer perceptrons.
CORPS_F: A NEW TOOL FOR FEATURE ASSESSMENT IN IMPRECISELY SUPERVISED OR FUZZY ENVIRONMENTS
Authors: DASARATHY BELUR V.
Published: November 2004

This study presents an effective approach to the hitherto little addressed problem of feature assessment and selection for pattern recognition in imprecisely supervised environments. Unlike in classical supervised environments wherein the representative training samples have crisp class labels, here the samples have fuzzy memberships in several of the different pattern classes in the environment. The new methodology reported here is an outgrowth of a recently developed tool CORPS—Class Overlap Region Partitioning Scheme initially designed for operation in supervised environments and extended later for operation in imperfectly supervised environments. The emphasis here has been the development of a computationally efficient scheme capable of evaluating as rapidly as practical a large number of features individually as to their discrimination potential based on which a smaller subset may be selected, if so desired, for more detailed evaluation in different combinations by other tools.
AN OVERVIEW OF REFLECTION AND ITS USE IN COOPERATION
Authors: EDMOND DAVID , PAPAZOGLOU MIKE , TARI ZAHIR
Published: November 2004

This paper describes a number of approaches to the development of more intelligent and more adaptable software. The paper introduces the notion of reflection and surveys two major styles: task and programming reflection. The paper then introduces a new form, viz operational reflection, based on the integration of these styles. This form of reflection is applied to cooperative environments and enables local database systems to be surrounded by a layer of meta-level software. This is used to capture domain and operational knowledge, and to describe, at least in part, remote systems and to monitor task-oriented activities. Thus we can turn a set of discrete database systems into a cooperative environment.
INTEROPERABLE QUERY PROCESSING FROM OBJECT TO RELATIONAL SCHEMAS BASED ON A PARAMETERIZED CANONICAL REPRESENTATION
Authors: RASCHID LOUIQA , CHANG YA-HUI
Published: November 2004

In this paper, we develop techniques for interoperable query processing between object and relational schemas. The objective is to pose a query against a local object schema and be able to share information transparently from target relational databases. Our approach is a mapping approach (as opposed to a global schema approach) and is based on using canonical representations (CR). We use one CR for resolving heterogeneity based on the object and relational query languages. We use a second parameterized CR to resolve representational heterogeneity between object and relational schema, and to build a mapping knowledge dictionary. There is also a set of mapping rules, based on the parameters of the CR, which defines the appropriate mapping between schemas. A query posed against the local object schema is first represented in the CR for queries, and then transformed by the mapping rules, to an appropriate query for the target relational schema, using relevant information from the mapping knowledge dictionary. The use of the parameterized CR allows us to build the mapping knowledge dictionary easily, and allows reusability of the mapping rules.
FROM E-R TO “A-R” — MODELLING STRATEGIC ACTOR RELATIONSHIPS FOR BUSINESS PROCESS REENGINEERING
Authors: YU ERIC S.K. , MYLOPOULOS JOHN
Published: November 2004

As information systems are increasingly expected to work with humans cooperatively in complex organizational contexts, conceptual modelling techniques need to be extended to relate information structures and processes to business and organizational objectives. We propose a framework which focuses on the modelling of strategic actor relationships (“A-R”) for a richer conceptual model of business processes in their organizational settings. Organizations are viewed as being made up of social actors who are intentional — have motivations, wants, and beliefs — and strategic — they evaluate their relationships to each other in terms of opportunities and vulnerabilities. The framework supports formal modelling of the network of dependency relationships among actors, and the systematic exploration and assessment of alternative process designs in reengineering. The semantics of the modelling concepts are axiomatically characterized. By embedding the framework in the Telos language, the framework can also potentially serve as an early-requirements phase tool in a comprehensive information system development environment.
BUSINESS PROCESS MODELING AND WORKFLOW MANAGEMENT
Authors: GRUHN VOLKER
Published: November 2004

Most of today’s approaches to business process engineering (also called business process management) start from an activity-centered perspective. They describe activities to be carried out within a business process and their relationships, but they usually pay little attention to the objects manipulated within processes. In this article, we discuss an approach to business process modeling, model analysis, and business process enaction (also called workflow management) which is based on data modeling, activity modeling, and organization modeling. In fact, the ℒeu approach to business process management considers data models (describing types of objects to be manipulated in a business process and their relationships), activity models (describing activities to be carried out in a business process), and organization models (describing organizational entities involved in a business process) as separate, but equally important, facets of business processes.
MODELLING IN COORDINATION SYSTEMS
Authors: NORRIE M. C. , WUNDERLI M.
Published: November 2004

We describe an approach to the coordination of application systems based on the modelling and maintenance of inter-system dependencies expressed as data constraints together with update propagation rules. These dependencies are specified by a Coordination Model which comprises a Coordination Interface for each application system together with a global Coordination View. A Coordination Interface describes local object types relevant for system-wide coordination. The Coordination View describes the subsystems, their globally important object types and the relationships between those object types. Additionally, the Coordination View specifies actions to restore global consistency in the event of constraint violations, thereby providing system coordination. Specifically, we describe how this approach has been adopted in a prototype Computer Integrated Manufacturing (CIM) system based on the coordination of CIM subsystems. In this CIM system, the Coordination Model is specified using the NIAM data model.
AN EXECUTABLE META MODEL FOR RE-ENGINEERING OF DATABASE SCHEMAS
Authors: JEUSFELD MANFRED A. , JOHNEN UWE A.
Published: November 2004

A logical database schema, e.g. a relational one, is the implementation of a specification, e.g. an entity-relationship diagram. Upcoming new data models require a cost-effective method for mapping from one data model to the other. We present an approach where the mapping process is divided into three parts. The first part reformulates the source and target data models into a so-called meta model. The second part classifies the input schema into the meta model, yielding a data model-independent representation. The third part synthesizes the output schema in terms of the target data model. The meta model, the data models as well as the schemas are all represented in the logic-based formalism of O-Telos. Its ability to quantify across data model concepts is the key to classifying schema elements independently of their data model. A prototype has been implemented on top of the deductive object base manager ConceptBase for the mapping of relational schemas to entity-relationship diagrams. From this, a C++-based tool has been derived as part of a commercial CASE environment for database applications.
A DISTRIBUTED AND ANONYMOUS KNOWLEDGE SHARING APPROACH TO SOFTWARE INTEROPERATION
Authors: SINGH NARINDER , GENESERETH MICHAEL , SYED MUSTAFA
Published: November 2004

The support for automatic interoperation of software components can reduce cost and provide greater functionality. This paper describes a novel approach to software interoperation based on specification sharing. Software components, called agents, provide machine processable descriptions of their capabilities and needs. Agents can be realized in different programming languages, and they can run in different processes on different machines. In addition, agents can be dynamic — at run time agents can join the system or leave. The system uses the declarative agent specifications to automatically coordinate their interoperation. The architecture supports anonymous interoperation of agents, where each agent has the illusion that the capabilities of all the other agents are provided directly by the system. The distinctive feature of this approach is the expressiveness of the declarative specification language, which enables sophisticated agent interoperation, e.g. decomposing complex requests into a collection of simpler requests, and translating between the interface of a requesting agent and the interface of an agent that can service the request. The agent-based interoperation scheme relies on a shared vocabulary, and it is our thesis that more effective software interoperation is made possible by agreeing to a shared declarative vocabulary, than by agreeing to procedural interface specifications that do not address the semantics of the software component (e.g. object interface specifications in an object-oriented programming environment).
DRESSED EXCITONS IN MICROCAVITY
Authors: HANAMURA E. , INOUE J. , YURA F.
Published: November 2004

After reviewing the important roles of excitons in nonlinear optical responses, we demonstrate mutual and quantum-mechanical control of radiation field and excitons on the same footing in a microcavity. First we introduce dressed excitons as bosons interacting coherently and reversibly with a radiation mode in the microcavity. Although the vacuum Rabi splitting of the dressed exciton is the same as that of dressed atom, the emission spectrum under strong pumping shows quartet structure different from the triplet of dressed atom. Secondly, the population dynamics of dressed excitons, i.e., one-dimensional polaritons in the mesoscopic system is solved and the dominant distribution on a single mode is demonstrated above the critical pumping.