text:
# hypertypes: Typed ASTs

#### Maintainer's Corner

For package maintainers and hackage trustees

Candidates

• No Candidates
Versions [RSS] 0.1.0.1, 0.1.0.2 ChangeLog.md array, base (>=4.9 && <5), base-compat, binary, constraints, containers, deepseq, generic-constraints, generic-data, lattices, lens, monad-st, mtl, pretty, QuickCheck, show-combinators, template-haskell, th-abstraction (>=0.3), transformers [details] BSD-3-Clause 2018 Yair Chuchem" Yair Chuchem yairchu@gmail.com Algorithms, Compilers/Interpreters, Language, Logic, Unification https://github.com/lamdu/hypertypes#readme https://github.com/lamdu/hypertypes/issues head: git clone https://github.com/lamdu/hypertypes by YairChuchem at 2021-06-23T10:08:07Z NixOS:0.1.0.2 203 total (9 in the last 30 days) (no votes yet) [estimated by Bayesian average] λ λ λ Docs available Last success reported on 2021-06-23

[back to package description]

# hypertypes: Types parameterised by hypertypes

Hypertypes enable constructing rich recursive types from individual components, and processing them generically with type classes.

They are a solution to the Expression Problem, as described by Phil Wadler (1998):

The goal is to define a data type by cases, where one can add new cases to the data type and new functions over the data type, without recompiling existing code, and while retaining static type safety.

Data types a la carte (DTALC, Swierstra, 2008) offers a solution for the expression problem which is only applicable for simple recursive expressions, without support for mutually recursive types. In practice, programming language ASTs do tend to be mutually recursive. multirec (Rodriguez et al, 2009) uses GADTs to encode mutually recursive types but in comparison to DTALC it lacks in the ability to construct the types from re-usable components.

Hypertypes allow constructing expressions from re-usable terms like DTALC, which can be rich mutually recursive types like in multirec.

The name "Hypertypes" is inspired by Hyperfunctions (S. Krstic et al, FICS 2001), which are a similar construct at the value level.

## Introduction to the "field constructor" pattern

### Type: Simple type, simple functionality

Suppose we have the following type in an application:

data Person = Person
{ height :: Double
, weight :: Double
}

Let's imagine that we want to let a user fill in a Person via a form, where during the process the record may have missing fields.

We may want a way to represent a state with missing fields, but this type doesn't allow for it.

We can either create an additional type for that, or augment Person to provide more functionality. Augmenting Person is preferred because it will result in less boiler-plate and less types to maintain as we make changes to it.

### Type -> Type: Adding a type parameter

A possible solution is to parameterize Person on the field type:

data Person a = Person
{ height :: a
, weight :: a
}

This would solve our problem.

We can parameterize with Double for the normal structure, and with Maybe Double for the variant with missing fields.

This approach reaches its limits when the fields have multiple different types, as in:

data Person = Person
{ height :: Double
, weight :: Double
, name :: Text
}

We would now need an additional parameter to parameterize how to store the fields of type Text! Is there a way to use a single type parameter for both types of fields? Yes, there is:

### (Type -> Type) -> Type: Higher-Kinded Data

The "Higher-Kinded Data" pattern represents Person like so:

data Person f = Person
{ height :: f Double
, weight :: f Double
, name :: f Text
}

For the plain case we would use Person Identity.

Identity from Data.Functor.Identity is defined as so:

data Identity a = Identity a

And for the variant with missing fields we would use Person Maybe.

The benefit of this parameterization over the previous one is that Person's kind doesn't need to change when adding more field types, so such changes don't propagate all over the code base.

Note that various helper classes such as Rank2.Functor and Rank2.Traversable (from the rank2classes package) allow us to conveniently convert between Person Identity and Person Maybe.

#### HKD for nested structures

Let's employ the same transformation we did for Person to a more complicated data structure:

data Expr
= Const Int
| Mul Expr Expr

The HKD form of Expr would be:

data Expr f
= Const (f Int)
| Add (f (Expr f)) (f (Expr f))
| Mul (f (Expr f)) (f (Expr f))

This does allow representing nested structures with missing elements. But classes like Rank2.Functor no longer work for it. To understand why let's look at Rank2.Functor's definition

class Functor f where
(<\$>) :: (forall a. p a -> q a) -> f p -> f q

The rank-2 function argument expects the field type a to stay the same when it changes p to q, however in the above formulation of Expr the field type Expr p change to Expr q when changing the type parameter.

### Type -> Type: The DTALC and recursion-schemes approach

Another formulation of Expr is the same as the Type -> Type approach discussed above:

data Expr a
= Const Int
| Mul a a

Notes:

• The recursion-schemes package can generate this type for us from the plain definition of Expr using TemplateHaskell
• DTALC also allows us to construct this type by combining standalone Const, Add, and Mul types with the :+: operator (i.e Const Int :+: Add :+: Mul)

This approach does have the single node type limitation, so we gave up on parameterizing over the Int in Const. This is a big limitation, but as we'll see, we do get several advantages in return.

First, we can represent plain expressions as Fix Expr, using:

newtype Fix f = Fix (f (Fix f))

We can then use useful combinators from recursion-schemes for folding and processing of Exprs.

unification-fd is a good example of the power of this approach. It implements generic unification for ASTs, where it uses the parameterization to represent sub-expressions via unification variables.

In constrast to the HKD approach, we can also use rich fix-points which store several different fix-points within, like Diff:

data Diff f
= Same (f (Fix f))
| SameTopLevel (f (Diff f))
| Different (f (Fix f)) (f (Fix f))

(Note how Diff parameterizes f by both Fix and Diff)

The main drawback of this approach is that in practice ASTs tend to be mutually recursive datatypes. For example:

data Expr
= Var Text
| App Expr Expr
| Lam Text Typ Expr
data Typ
= IntT
| FuncT Typ Typ

This type is an example for an AST which DTALC and recursion-schemes cannot represent.

Can the "field constructor" pattern be used to represent such ASTs? Yes:

### (Index -> Type) -> Index -> Type: The multirec approach

multirec's way to define the above AST:

data Expr :: Index
data Typ :: Index

data AST :: (Index -> Type) -> Index -> Type where
Var :: Text -> AST r Expr
App :: r Expr -> r Expr -> AST r Expr
Lam :: Text -> r Typ -> r Expr -> AST r Expr
IntT :: AST r Typ
FuncT :: r Typ -> r Typ -> AST r Typ

(this is a slight variant of multirec's actual presentation, where for improved legibility Index is used rather than Type)

multirec offers various utilities to process such data types. It offers HFunctor, a variant of Functor for these structures, and various recursive combinators.

But multirec has several limitations:

• Using a single GADT for the data type limits composition and modularity.
• Invocations of HFunctor for a Typ node need to support transforming all indices of AST, including Expr, even though Typ doesn't have Expr child nodes.

## hypertypes's approach

The hypertypes representation of the above AST example:

data Expr h
= EVar Text
| EApp (h :# Expr) (h :# Expr)
| ELam Text (h :# Typ) (h :# Expr)
data Typ h
= TInt
| TFunc (h :# Typ) (h :# Typ)

Sub-expressions are nested using the :# type operator. On the left side of :# is Expr's type parameter h which is the "nest type", and on the right side Expr and Typ are the nested nodes.

:# is defined as:

-- A type parameterized by a hypertype
type HyperType = AHyperType -> Type

-- A kind for hypertypes
newtype AHyperType = AHyperType { getHyperType :: HyperType }

-- GetHyperType is getHyperType lifted to the type level
type family GetHyperType h where
GetHyperType ('AHyperType t) = t

type p :# q = (GetHyperType p) ('AHyperType q)
-- AHyperType is DataKinds syntax for using AHyperType in types

The hypertypes library provides:

• Variants of standard classes like Functor with TemplateHaskell derivations for hypertypes. (Unlike in multirec's HFunctor, only the actual child node types of each node need to be handled)
• Combinators for recursive processing and transformation of nested structures
• Implementations of common AST terms
• A unification implementation for mutually recursive types inspired by unification-fd
• A generic and fast implementation of Hindley-Milner type inference ("Efficient generalization with levels" as described in How OCaml type checker works, Kiselyov, 2013)

## Constructing types from individual components

Note that another way to formulate the above expression would be using pre-existing parts, such as:

data RExpr h
= RVar (Var Text RExpr h)
| RApp (App RExpr h)
| RLam (TypedLam Text Typ RExpr h)
deriving (Generic, Generic1, HNodes, HFunctor, HFoldable, HTraversable, ZipMatch)

This form supports using DeriveAnyClass to derive instances for various HyperType classes such as HFunctor based on Generic1. Note that due to a technical limitation of Generic1 the form of Expr from before, which directly nests values, doesn't have a Generic1 instance (so the instances for Expr are derived using TemplateHaskell instead).

## Examples

How do we represent an expression of the example language declared above?

verboseExpr :: Pure # Expr
verboseExpr =
Pure (ELam "x" (Pure TInt) (Pure (EVar "x")))

Explanations for the above:

• Pure # Expr is a type synonym for Pure ('AHyperType Expr)
• Pure is the simplest "pass-through" nest type
• The above is quite verbose with a lot of instances of Pure and many parentheses
• Writing an expression of the above RExpr would be even more verbose due to additional Var and TypedLam data constructors!

To write it more consicely, the HasHPlain class, along with a TemplateHaskell generator for it, exists:

> let e = hPlain :# verboseExpr
-- Note: This (#) comes from Control.Lens

> e
ELamP "x" TIntP (EVarP "x")

> :t e
e :: HPlain Expr

It's now easier to see that e represents λ(x:Int). x

HPlain is a data family of "plain versions" of expressions, generated via TemplateHaskell. Note that it flattens embedded constructors for maximal convinience, so that the plain version of RExpr is as convinient to use as that of Expr!

This is somewhat similar to how recursion-schemes can derive a parameterized version of an AST, but is the other way around: the parameterized type is the source and the plain one is generated.

So now, let's define some example expressions concisely:

exprA, exprB :: HPlain Expr

exprA = ELamP "x" IntTP (EVarP "x")

exprB = ELamP "x" (TFuncP TIntP TIntP) (EVarP "x")

What can we do with these expressions? Let's compute a diff:

> let d = diffP exprA exprB

> d
CommonBodyP
(ELam "x"
(DifferentP TIntP (TFuncP TIntP TIntP))
(CommonSubTreeP (EVarP "x"))
)

> :t d
d :: DiffP # Expr
-- (An Expr with the DiffP nest type)

Let's see the type of diffP:

> :t diffP
diffP ::
( RTraversable h
, Recursively ZipMatch h
, Recursively HasHPlain h
) =>
HPlain h -> HPlain h -> DiffP # h

diffP can compute the diff for any AST that is recursively traversable, can be matched, and has a plain representation.

Now, let's format this diff better:

> let formatDiff _ x y = "- " <> show x <> "\n+ " <> show y <> "\n"

> putStrLn (foldDiffsP formatDiff d)
- TIntP
+ TFuncP TIntP TIntP

> :t foldDiffsP
foldDiffsP ::
( Monoid r
, Recursively HFoldable h
, Recursively HasHPlain h
) =>
(forall n. HasHPlain n => HRecWitness h n -> HPlain n -> HPlain n -> r) ->
DiffP # h ->
r

Why is the ignored argument of formatDiff there? It is the HRecWitness h n from the type of foldDiffsP above. It is a witness that "proves" that the folded node n is a recursive node of h, essentially restricting the forall n. to ns that are recursive nodes of h.

## Witness parameters

First, I want to give thanks and credit: We learned of this elegant solution from multirec!

What are witness parameters?

Let's look at how HFunctor is defined:

class HNodes h => HFunctor h where
-- | 'HFunctor' variant of 'fmap'
hmap ::
(forall n. HWitness h n -> p # n -> q # n) ->
h # p ->
h # q

HFunctor can change an h's nest-type from p to q.

HWitness is a data family which is a member of HNodes.

For example, let's see the definition of Expr's HWitness:

data instance HWitness Expr n where
W_Expr_Expr :: HWitness Expr Expr
W_Expr_Typ :: HWitness Expr Typ

Note that this GADT is automatically generated via TemplateHaskell.

What does the witness give us? It restricts forall n. to the nodes of h. When mapping over an Expr we can:

• Ignore the witness and use a mapping from a p of any n to a q of it
• Pattern match on the witness to handle Expr's specific node types
• Use the #> operator to convert the witness to a class constraint on n.

## Understanding HyperTypes

• We want structures to be parameterized by nest-types
• Nest-types are parameterized by the structures, too
• Therefore, structures and their nest-types need to be parameterized by each other
• This results in infinite types, as the structure is parameterized by something which may be parameterized by the structure itself.

multirec ties this knot by using indices to represent types. hypertypes does this by using DataKinds and the AHyperType newtype which is used for both structures and their nest-types. An implication of the two being the same is that the same classes and combinators are re-used for both.

hypertypes is implemented with GHC and heavily relies on quite a few language extensions:

• ConstraintKinds and TypeFamilies are needed for the HNodesConstraint type family that lifts a constraint to apply over a value's nodes. Type families are also used to encode term's results in type inference.
• DataKinds allows parameterizing types over AHyperTypes
• DefaultSignatures are used for default methods that return Dicts to avoid undecidable super-classes
• DeriveGeneric, DerivingVia, GeneralizedNewtypeDeriving, StandaloneDeriving and TemplateHaskell are used to derive type-class instances
• EmptyCase is needed for instances of leaf nodes
• FlexibleContexts, FlexibleInstances and UndecidableInstances are required to specify many constraints
• GADTs and RankNTypes enable functions like hmap which get foralled functions with witness parameters
• MultiParamTypeClasses is needed for the Unify and Infer type classes
• ScopedTypeVariables and TypeApplications assist writing short code that type checks

Many harmless syntactic extensions are also used:

• DerivingStrategies, LambdaCase, TupleSections, TypeOperators

Some extensions we use but would like to avoid (we're looking for alternative solutions but haven't found them):

## How does hypertypes compare/relate to

Note that comparisons to multirec, HKD, recursion-schemes, rank2classes, and unification-fd were discussed above.

### hyperfunctions

S. Krstic et al [KLP2001] have described the a type which they call a "Hyperfunction". Here is it's definition from the hyperfunctions package:

newtype Hyper a b = Hyper { invoke :: Hyper b a -> b }

AHyperTypes are isomorphic to Hyper Type Type (assuming a PolyKinds variant of Hyper), so they can be seen as type-level "hyperfunctions".

For more info on hyperfunctions and their use cases in the value level see [LKS2013]

#### References

• [KLP2001] S. Krstic, J. Launchbury, and D. Pavlovic. Hyperfunctions. In Proceeding of Fixed Points in Computer Science, FICS 2001
• [LKS2013] J. Launchbury, S. Krstic, T. E. Sauerwein. Coroutining Folds with Hyperfunctions. In In Proceedings Festschrift for Dave Schmidt, EPTCS 2013

### Data Types a la Carte

In addition to the external fix-points described above, Data Types a la Carte (DTALC) also describes how to define ASTs structurally.

I.e, rather than having

data Expr a
= Val Int
| Add a a -- "a" stands for a sub-expression (recursion-schemes style)

We can have

newtype Val a = Val Int

-- Expr is a structural sum of Val and Add
type Expr = Val :+: Add

This enables re-usability of the AST elements Val and Add in various ASTs, where the functionality is shared via type classes. Code using these type classes can work generically for different ASTs.

Like DTALC, hypertypes has:

• Instances type for combinators such as :+: and :*:, so that these can be used to build ASTs
• Implementations of common AST terms in the Hyper.Type.AST module hierarchy (App, Lam, Let, Var, TypeSig and others)
• Classes like HFunctor, HTraversable, Unify, Infer with instances for the provided AST terms

As an example of a reusable term let's look at the definition of App:

-- | A term for function applications.
data App expr h = App
{ _appFunc :: h :# expr
, _appArg :: h :# expr
}

Unlike a DTALC-based apply, which would be parameterized by a single type parameter (a :: Type), App is parameterized on two type parameters, (expr :: HyperType) and (h :: AHyperType). expr represents the node type of App expr's child nodes and h is the tree's fix-point. This enables using App in mutually recursive ASTs where it may be parameterized by several different exprs.

Unlike the original DTALC paper which isn't suitable for mutually recursive ASTs, in hypertypes one would have to declare an explicit expression type for each expression type for use as App's expr type parameter. Similarly, multirec's DTALC variant also requires explicitly declaring type indices.

While it is possible to declare ASTs as newtypes wrapping :+:s of existing terms and deriving all the instances via GeneralizedNewtypeDeriving, our usage and examples declare types in the straight forward way, with named data constructors, as we think results in more readable and performant code.

### bound

bound is a library for expressing ASTs with type-safe De-Bruijn indices rather than parameter names, via an AST type constructor that is indexed on the variables in scope.

An intereseting aspect of bound's ASTs is that recursively they are made of an infinite amount of types.

When implementing hypertypes we had the explicit goal of making sure that such ASTs are expressible with it, and for this reason the Hyper.Type.AST.NamelessScope module in the tests implementing it is provided, and the test suite includes a language implementation based on it (LangA in the tests).

### lens

hypertypes strives to be maximally compatible with lens, and offers Traversals and Setters wherever possible. But unfortunately the RankNTypes nature of many combinators in hypertypes makes them not composable with optics. For the special simpler cases when all child nodes have the same types the htraverse1 traversal and hmapped1 setter are available.


text:
## Section30.6Gauss's Law Bootcamp

### Subsection30.6.3Miscellaneous

A point charge $q$ is at the center of a cube of side $a\text{.}$ Find the electric flux through one of its sides.

Hint

Think how you can use Gauss's law for closed surface.

$\dfrac{1}{6}\:\dfrac{q}{\epsilon_0}\text{.}$

Solution

By Gauss's law, flux through a closed surface equals $q_\text{enc}/\epsilon_0\text{.}$ Now, if we consider the surfaces of the cube making a closed surface around the charge at the center,we will have

\begin{equation*} \Phi_{\text{cube}} = \frac{q}{\epsilon_0}. \end{equation*}

Since the charge is at the center of the cube, we can assert that flux through each face of the cube will be same based on the symmetry.

\begin{equation*} \Phi_{\text{cube}} = 6\times \Phi_{\text{one face}}. \end{equation*}

Therefore, we will have

\begin{equation*} \Phi_{\text{one face}} = \dfrac{1}{6}\:\dfrac{q}{\epsilon_0}. \end{equation*}

A charge $q$ is placed at one of the corners of a cube of side $a\text{.}$ Find the electric flux through the shaded face shown in the figure. Assume $q>0\text{.}$

Hint

Think of enclosing the charge symmetrically by a larger cube, and the, use Gauss's law on the larger cube.

$\dfrac{1}{24}\:\dfrac{q}{\epsilon_0}\text{.}$

Solution

Since the charge is at one corner of the cube, we do not have a symmetry like the one we had when the charge was located at the center of the cube in Problem 30.6.18.

However, we can imagine adding seven more cubes to form a larger cube of side $2a$ so that the charge now sits at the center of the larger cube. According to Gauss's law, the electric flux trough the surface of the larger cube will be

\begin{equation*} \Phi_{\text{larger cube}} = \dfrac{q}{\epsilon_0}. \end{equation*}

Now, there are $8$ smaller cubes, each with $3$ faces in the same symmetric situation. This makes net flux equal to $8\times 3=24$ times the surface of the original face. Therefore, flux through the shaded face of the original cube will be

\begin{equation*} \Phi_{\text{larger cube}} = 24\times \Phi_{\text{shaded face original}}. \end{equation*}

Therefore, the flux through the shaded face of the original cube will be

\begin{equation*} \Phi_{\text{shaded face original}} = \dfrac{1}{24}\:\dfrac{q}{\epsilon_0}. \end{equation*}

Two non-conducting uniformly charged thin straight wires of line charge densities $\lambda_1=\lambda_0$ and $\lambda_2=-\lambda_0$ respectively are placed a distance $2d$ apart as shown in Figure 30.6.21.

Suppose the wires are parallel to the $z$ axis and cross the $xy$-plane on the $x$ axis at $x_1= -d$ and $x_2= +d\text{,}$ respectively. Find electric field at a point P in the $xy$-plane. Numerical values to use: $\lambda_0 = 10\ \mu\text{C/m}\text{,}$ $d=1.0\text{ cm}\text{,}$ $x = 2\text{ cm}\text{,}$ and $y = 4\text{ cm}\text{.}$

Hint

Use superposition of the electric field of the electric fields of the two wores. Pay attention to the directions.

$37,500\text{ N/C}$ at clockwise angle $82^\circ$ from positive $x$-axis.

Solution

I will work out the numerical problem.

Let $r_1$ and $r_2$ be the distance from the wires to the field point $(x,y)$ in the $xy$-plane .

\begin{align*} r_1 \amp = \sqrt{(x+d)^2 + y^2}, \\ \amp = \sqrt{(2+1)^2 + 4^2} = 5\text{ cm}, \\ r_2 \amp = \sqrt{(x-d)^2 + y^2}, \\ \amp = \sqrt{(2-1)^2 + 4^2} = \sqrt{17}\text{ cm}. \end{align*}

Using the formulas for the magnitudes of the electric fields from charges on long wire, which is done by Gauss's law for cyclindrical case, we get

\begin{align*} E_1 \amp = \dfrac{|\lambda_1|}{2\pi\epsilon_0}\,\dfrac{1}{r_1} \\ \amp = \dfrac{ 10\times 10^{-6}}{2\pi\times8.85\times 10^{-12}}\,\dfrac{1}{5} = 35,967\text{ N/C} \\ E_2 \amp = \dfrac{|\lambda_2|}{2\pi\epsilon_0}\,\dfrac{1}{r_2} \\ \amp = \dfrac{ 10\times 10^{-6}}{2\pi\times8.85\times 10^{-12}}\,\dfrac{1}{\sqrt{17}} = 67,972\text{ N/C} \end{align*}

Now we need to add them vectorially. The net field is not just sum of the magnitudes, as you know from vector addition.

\begin{equation*} E_P \ne E_1 + E_2. \end{equation*}

We will first compute $x$ and $y$ components of the two fields so that we can find $x$ and $y$ components of the net field.

\begin{align*} E_{1x} \amp = E_1\, \dfrac{x+d}{r_1}, \\ \amp = 35,967\text{ N/C}\, \dfrac{3}{5} = 21,580\text{ N/C}, \\ E_{1y} \amp = E_1\, \dfrac{y}{r_1}, \\ \amp = 35,967\text{ N/C}\, \dfrac{4}{5} = 28,774\text{ N/C}. \end{align*}

Similarly, we work out the components of the field of wire 2. But, here we need to multiply by $-1$ since we have a negative charge.

\begin{align*} E_{2x} \amp = E_2\, \dfrac{-(x-d)}{r_2}, \\ \amp = 67,972\text{ N/C}\, \dfrac{-1}{\sqrt{17}} = -16,486\text{ N/C}, \\ E_{2y} \amp = E_2\, \dfrac{-y}{r_2}, \\ \amp = 67,972\text{ N/C}\, \dfrac{-4}{\sqrt{17}} = -65,943\text{ N/C}. \end{align*}

Therefore, the components of the net field are

\begin{align*} E_x \amp = E_{1x} + E_{2x} = 21,580 -16,486 = 5,094\text{ N/C},\\ E_y \amp = E_{1y} + E_{2y} = 28,774 - 65,943 = -37,169\text{ N/C} \end{align*}

Therefore, the magnitude of the field is

\begin{equation*} E = \sqrt{ E_x^2 + E_y^2} = 37,500\text{ N/C}, \end{equation*}

and the direction can be given by clockwise angle from positive $x$ axis.

\begin{equation*} \theta = \tan^{-1}\left( \dfrac{-37,169}{5,094} \right) = - 82^\circ. \end{equation*}

A disk of radius $R$ is cut in a non-conducting large plate that is uniformly charged with charge density $\sigma$ (coulomb per square meter). Find the electric field at a height $h$ above the center of the disk. ($h>>R\text{,}$ $h\lt \lt l$ or $w$).

Hint

Fill hole with $\pm\sigma$ and then use superposition of plane of charge and a disk.

$\dfrac{\sigma h}{2\epsilon_0\,\sqrt{R^2+h^2}}\text{.}$

Solution

Imagine filling the hole with equal and opposite charge with charge densities $+\sigma$ and $-\sigma\text{.}$ When we include the small disk of charge $+\sigma$ with the rest of the plane, we get one large plane of charge density $+\sigma\text{.}$ The charge compensating disk of charge density $-\sigma$ can be treated as a separate disk. The electric field at point P will be equal to the vector sum of the field of the entire plane and of the disk.

We know the formulas for the electric fields of large uniformly charged plate and of a uniformly charged disk. Here the field from the plane is pointed away from the plane and the field of the disk is towards the plane.

With $z$ axis pointed up, the $z$ components of electric fields from plate and disk are

\begin{align*} E_{\text{plate},z} \amp = \dfrac{\sigma}{2\epsilon_0},\\ E_{\text{disk},z} \amp = -\dfrac{\sigma}{2\epsilon_0}\: \left( 1-\dfrac{h}{\sqrt{R^2 + h^2}} \right). \end{align*}

Adding these components of fields we obtain the $z$ component of the net electric field.

\begin{equation*} E_{z} = \dfrac{\sigma}{2\epsilon_0}\: \dfrac{h}{\sqrt{R^2 + h^2}} \end{equation*}

Since, the field has only $z$ component, this also is the magnitude of the net electric field. The direction will be away from the plate if $\sigma\gt 0$ and towards the plate if $\sigma\lt 0\text{.}$

A noncoducting sphere of radius $R$ has uniform charge density $\rho_0\text{.}$ A spherical cavity of radius $\frac{R}{2}$ is then removed, resulting in the configuration shown in Figure 30.6.24. Find electric field at points (a) $\text{P}_1\text{,}$ (b) $\text{P}_2\text{,}$ (c) $\text{P}_3\text{,}$ (d) $\text{P}_4\text{,}$ and (e) $\text{P}_5\text{.}$

Hint

Think filling the cavity with opposite charges and restoring spherical symmetry.

(a) $\frac{\rho_0 R}{6\epsilon_0}\text{,}$ left, (b) $\frac{\rho_0 R}{6\epsilon_0}\text{,}$ left, (c) $\frac{\rho_0 R}{6\epsilon_0}\text{,}$ left, (d) $\frac{17\rho_0 R}{54\epsilon_0}\text{,}$ right, (d) $\frac{5\rho_0 R}{216\epsilon_0}\text{,}$ right, (e)

Solution

As before in other problems with cavities, we will fill the cavity with opposite charges so that we can restore symmetries in charge distribution. Suppose, charge density $\rho_0$ is positive, then we will fill the cavity with positive $\rho_0$ and equal amout of negative $-\rho_0\text{.}$ Then, we include $\rho_0$ with the original charges.

This process makes two spherically symmetric charge distributions. Since we already know expressions for electric field in uniformly charged sphere, we will just use those formulas when we superimpose the answers.

We will work out directions for $\rho_0\gt 0\text{.}$ If $\rho_0\lt 0\text{,}$ you wil ljust have to flip the arrow.

(a) At $\text{P}_1\text{,}$ the field from smaller sphere will be to the right and field from the larger sphere will be to the left. This will mean they will subtract. The magnitudes of the two are such that both have contribution from all charges in their distributions since $\text{P}_1$ is outside of both - at the edge will be taken as just outside. Hence, magnitude of the field there will be

\begin{equation*} E_1 = \frac{\rho_0 R}{3\epsilon_0} - \frac{\rho_0 R/2}{3\epsilon_0} = \frac{\rho_0 R}{6\epsilon_0}. \end{equation*}

The direction is to the left.

(b) At $\text{P}_2\text{,}$ we have zero field from the smaller sphere. Since this point is an inside point for the larger sphere, we will use $E_\text{in}$ formula for that.

\begin{equation*} E_2 = \frac{\rho_0 R/2}{3\epsilon_0} = \frac{\rho_0 R}{6\epsilon_0}. \end{equation*}

The direction is to the left.

(c) At $\text{P}_3\text{,}$ we have zero field from the larger sphere. Since this point is an outside point for the smaller sphere, we will use $E_\text{out}$ formula for that. At the edge of this sphere we get

\begin{equation*} E_3 = \frac{\rho_0 R}{6\epsilon_0}. \end{equation*}

The direction is to the left.

(d) $\text{P}_4$ is outside of both spheres with larger one's field pointed to the right and smaller one's pointed left. From their superposition we get the magnitude

\begin{align*} E_4 \amp = \frac{\frac{4}{3}\pi R^3 \rho_0 }{4\pi R^2 \epsilon_0} - \frac{\frac{4}{3}\pi (R/2)^3 \rho_0 }{4\pi (3R/2)^2 \epsilon_0}\\ \amp = \frac{17}{54}\ \frac{\rho_0 R}{\epsilon_0}. \end{align*}

The direction is to the right.

(e) $\text{P}_5$ is outside of both spheres with larger one's field pointed to the right and smaller one's pointed left. From their superposition we get the magnitude

\begin{align*} E_4 \amp = \frac{\frac{4}{3}\pi R^3 \rho_0 }{4\pi (3R/2)^2 \epsilon_0} - \frac{\frac{4}{3}\pi (R/2)^3 \rho_0 }{4\pi R^2 \epsilon_0}\\ \amp = \frac{5}{216}\ \frac{\rho_0 R}{\epsilon_0}. \end{align*}

The direction is to the right.

A spherical shell of radius $R$ is charged uniformly with constant surface charge density $\sigma_0\text{.}$ A small piece of the shell is then removed, resulting in a hole in the spherical shell. Suppose the removed part is almost flat circular disk of radius $a\text{.}$ What is the electric field an infinitesimal distance $d$ above the center of the hole so that you can asume $d\lt lt a\text{?}$

You might find magnitude of electric field of a disk of radius $a$ and charge density $\sigma$ at a distance $d$ above the center to be

\begin{equation*} E = \frac{|\sigma|}{2\epsilon_0}\left( 1 - \frac{d}{\sqrt{d^2+a^2}}\right). \end{equation*}

For $d\lt\lt a\text{,}$ this simplifies to $\frac{|\sigma|}{2\epsilon_0}\text{.}$

Hint

Think filling the hole with opposite charges and restoring spherical symmetry with one and using the large sheet formula for the other.

$\sigma_0/2\epsilon_0$ radially out if $\sigma_0\gt 0\text{.}$

Solution

As before in other problems with cavities, we will fill the cavity with opposite charges so that we can restore symmetries in charge distribution. Suppose, charge density $\sigma_0$ is positive, then we will fill the cavity with positive $\sigma_0$ and equal amout of negative $-\sigma_0\text{.}$ Then, we include $\sigma_0$ with the original charges. Then, electric field at P will be a vector sum of the electric field by the spherical shell and the disk as shown in Figure 30.6.27.

Let us use a $z$ axis to take care of directions. By Gauss's law, we get electric field of the shell, which we will wrtie as $z$ component at point P.

\begin{equation*} E_{\text{shell},z} = \frac{4\pi R^2 \sigma_0}{4\pi R^2 \epsilon_0} = \frac{\sigma_0}{\epsilon_0}. \end{equation*}

Since $d \lt\lt a\text{,}$ the $z$ component of the electric field from the negative charges on the disk will be

\begin{equation*} E_{\text{disk},z} = -\frac{\sigma_0}{2\epsilon_0}. \end{equation*}

Therefore, magnitude is $\frac{\sigma_0}{2\epsilon_0}$ and direction is radially out from the center of the spherical shell.

format: plain


text:
## 66.17 Scheme theoretic closure and density

This section is the analogue of Morphisms, Section 29.7.

Lemma 66.17.1. Let $S$ be a scheme. Let $W \subset S$ be a scheme theoretically dense open subscheme (Morphisms, Definition 29.7.1). Let $f : X \to S$ be a morphism of schemes which is flat, locally of finite presentation, and locally quasi-finite. Then $f^{-1}(W)$ is scheme theoretically dense in $X$.

Proof. We will use the characterization of Morphisms, Lemma 29.7.5. Assume $V \subset X$ is an open and $g \in \Gamma (V, \mathcal{O}_ V)$ is a function which restricts to zero on $f^{-1}(W) \cap V$. We have to show that $g = 0$. Assume $g \not= 0$ to get a contradiction. By More on Morphisms, Lemma 37.45.6 we may shrink $V$, find an open $U \subset S$ fitting into a commutative diagram

$\xymatrix{ V \ar[r] \ar[d]_\pi & X \ar[d]^ f \\ U \ar[r] & S, }$

a quasi-coherent subsheaf $\mathcal{F} \subset \mathcal{O}_ U$, an integer $r > 0$, and an injective $\mathcal{O}_ U$-module map $\mathcal{F}^{\oplus r} \to \pi _*\mathcal{O}_ V$ whose image contains $g|_ V$. Say $(g_1, \ldots , g_ r) \in \Gamma (U, \mathcal{F}^{\oplus r})$ maps to $g$. Then we see that $g_ i|_{W \cap U} = 0$ because $g|_{f^{-1}W \cap V} = 0$. Hence $g_ i = 0$ because $\mathcal{F} \subset \mathcal{O}_ U$ and $W$ is scheme theoretically dense in $S$. This implies $g = 0$ which is the desired contradiction. $\square$

Lemma 66.17.2. Let $S$ be a scheme. Let $X$ be an algebraic space over $S$. Let $U \subset X$ be an open subspace. The following are equivalent

1. for every étale morphism $\varphi : V \to X$ (of algebraic spaces) the scheme theoretic closure of $\varphi ^{-1}(U)$ in $V$ is equal to $V$,

2. there exists a scheme $V$ and a surjective étale morphism $\varphi : V \to X$ such that the scheme theoretic closure of $\varphi ^{-1}(U)$ in $V$ is equal to $V$,

Proof. Observe that if $V \to V'$ is a morphism of algebraic spaces étale over $X$, and $Z \subset V$, resp. $Z' \subset V'$ is the scheme theoretic closure of $U \times _ X V$, resp. $U \times _ X V'$ in $V$, resp. $V'$, then $Z$ maps into $Z'$. Thus if $V \to V'$ is surjective and étale then $Z = V$ implies $Z' = V'$. Next, note that an étale morphism is flat, locally of finite presentation, and locally quasi-finite (see Morphisms, Section 29.36). Thus Lemma 66.17.1 implies that if $V$ and $V'$ are schemes, then $Z' = V'$ implies $Z = V$. A formal argument using that every algebraic space has an étale covering by a scheme shows that (1) and (2) are equivalent. $\square$

It follows from Lemma 66.17.2 that the following definition is compatible with the definition in the case of schemes.

Definition 66.17.3. Let $S$ be a scheme. Let $X$ be an algebraic space over $S$. Let $U \subset X$ be an open subspace.

1. The scheme theoretic image of the morphism $U \to X$ is called the scheme theoretic closure of $U$ in $X$.

2. We say $U$ is scheme theoretically dense in $X$ if the equivalent conditions of Lemma 66.17.2 are satisfied.

With this definition it is not the case that $U$ is scheme theoretically dense in $X$ if and only if the scheme theoretic closure of $U$ is $X$. This is somewhat inelegant. But with suitable finiteness conditions we will see that it does hold.

Lemma 66.17.4. Let $S$ be a scheme. Let $X$ be an algebraic space over $S$. Let $U \subset X$ be an open subspace. If $U \to X$ is quasi-compact, then $U$ is scheme theoretically dense in $X$ if and only if the scheme theoretic closure of $U$ in $X$ is $X$.

Proof. Follows from Lemma 66.16.3 part (3). $\square$

Lemma 66.17.5. Let $S$ be a scheme. Let $j : U \to X$ be an open immersion of algebraic spaces over $S$. Then $U$ is scheme theoretically dense in $X$ if and only if $\mathcal{O}_ X \to j_*\mathcal{O}_ U$ is injective.

Proof. If $\mathcal{O}_ X \to j_*\mathcal{O}_ U$ is injective, then the same is true when restricted to any algebraic space $V$ étale over $X$. Hence the scheme theoretic closure of $U \times _ X V$ in $V$ is equal to $V$, see proof of Lemma 66.16.1. Conversely, assume the scheme theoretic closure of $U \times _ X V$ is equal to $V$ for all $V$ étale over $X$. Suppose that $\mathcal{O}_ X \to j_*\mathcal{O}_ U$ is not injective. Then we can find an affine, say $V = \mathop{\mathrm{Spec}}(A)$, étale over $X$ and a nonzero element $f \in A$ such that $f$ maps to zero in $\Gamma (V \times _ X U, \mathcal{O})$. In this case the scheme theoretic closure of $V \times _ X U$ in $V$ is clearly contained in $\mathop{\mathrm{Spec}}(A/(f))$ a contradiction. $\square$

Lemma 66.17.6. Let $S$ be a scheme. Let $X$ be an algebraic space over $S$. If $U$, $V$ are scheme theoretically dense open subspaces of $X$, then so is $U \cap V$.

Proof. Let $W \to X$ be any étale morphism. Consider the map $\mathcal{O}(W) \to \mathcal{O}(W \times _ X V) \to \mathcal{O}(W \times _ X (V \cap U))$. By Lemma 66.17.5 both maps are injective. Hence the composite is injective. Hence by Lemma 66.17.5 $U \cap V$ is scheme theoretically dense in $X$. $\square$

Lemma 66.17.7. Let $S$ be a scheme. Let $h : Z \to X$ be an immersion of algebraic spaces over $S$. Assume either $Z \to X$ is quasi-compact or $Z$ is reduced. Let $\overline{Z} \subset X$ be the scheme theoretic image of $h$. Then the morphism $Z \to \overline{Z}$ is an open immersion which identifies $Z$ with a scheme theoretically dense open subspace of $\overline{Z}$. Moreover, $Z$ is topologically dense in $\overline{Z}$.

Proof. In both cases the formation of $\overline{Z}$ commutes with étale localization, see Lemmas 66.16.3 and 66.16.4. Hence this lemma follows from the case of schemes, see Morphisms, Lemma 29.7.7. $\square$

Lemma 66.17.8. Let $S$ be a scheme. Let $B$ be an algebraic space over $S$. Let $f, g : X \to Y$ be morphisms of algebraic spaces over $B$. Let $U \subset X$ be an open subspace such that $f|_ U = g|_ U$. If the scheme theoretic closure of $U$ in $X$ is $X$ and $Y \to B$ is separated, then $f = g$.

Proof. As $Y \to B$ is separated the fibre product $Y \times _{\Delta , Y \times _ B Y, (f, g)} X$ is a closed subspace $Z \subset X$. As $f|_ U = g|_ U$ we see that $U \subset Z$. Hence $Z = X$ as $U$ is assumed scheme theoretically dense in $X$. $\square$

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).


text:
# Irreducibility of the Jacobians of a curves.

I'm studying Jacobian varieties.I assume that the existence of the Jacobian variety for a curve and attempt to show irreducibility of the Jacobian for a curve according to Remark:IV.4.10.9 of Hartshorne's book.

Let $$C$$ be a complete smooth curve of genus $$g$$ over an algebraic field $$k$$, let $$P_0 \in C$$ and let $$J(C)$$ is the Jacobian of C. By the universal property of the Jacobian, we can obtain the morphism $$\varphi : C^g \rightarrow J(C)$$ such that $$\varphi(k): C(k) \ni(P_1 ,\dots,P_n) \mapsto \mathcal{O}_C(P_0+\dots+P_n-nP_0)\in J(C)(k)=\mathrm{Pic}^\circ(C)$$. Then there exists an open subset $$U$$ of $$J(C)$$ such that the fibers of $$\varphi$$ at any point of U are finite sets. My book conclude that this means $$J(C)$$ is irreducible. But I cannot understand this. Could someone please tell me this reason?

• Searching for "jacobian hyperelliptic curve" shows many texts about the construction of the abelian group $Pic^0(C)$ and its algebraized variety – reuns Dec 14 '18 at 15:55


text:
# Triangle Drawn to a Circle

Geometry Level 2

Given circle $$\Gamma$$, point $$A$$ is chosen outside of $$\Gamma$$. Tangents $$AB$$ and $$AC$$ to $$\Gamma$$ are drawn. $$K$$ is a point on the circumference of $$\Gamma$$ contained within $$ABC$$. $$D$$ is a point on $$AB$$ and $$E$$ is a point on $$AC$$ such that $$DKE$$ is a straight line and tangent to $$\Gamma$$. If $$AB = 19$$, what is the perimeter of triangle $$ADE$$?

×


text:
# $\mathbb{Z}$ vs. $\hat{\mathbb{Z}}$ coefficents in Singular Cohomology

Let $X$ be a finite CW complex, given singular cohomology with coefficents in $\hat{\mathbb{Z}}$, $H^i(X, \hat{\mathbb{Z}})$ can you recover singular cohomology with coefficents in $\mathbb{Z}$?

I was told that one cannot do this.

However, it seems to be true. The singular cohomology groups are finitely generated abelian groups.

1.) We can recover the rank of each of them, because in our case $H^i(X, \hat{\mathbb{Z}}) \cong H^i(X, \mathbb{Z}) \otimes_{\mathbb{Z}} \hat{\mathbb{Z}}$.

2.) Thus, the issue is to recover the torsion. However, for every integer $m$, $\mathbb{Z}/m\mathbb{Z} \otimes_{\mathbb{Z}} \hat{\mathbb{Z}} \cong \mathbb{Z}/m\mathbb{Z}$ as $\mathbb{Z}$-modules.

$\textbf{Question: }$ Am I making a terrible mistake somewhere? More generally, it seems like the same trivial proof above shows that for any CW complex with finitely generated cohomology groups, one can easily recover cohomology with $\mathbb{Z}$ coefficents from $\hat{\mathbb{Z}}$-coefficents.

I'd really like to see a proof or a counterexample.

-
clarification needed; you mean the profinite completion of $\mathbb{Z}$? –  Bombyx mori Jan 10 '13 at 6:28
Yes, $\hat{\mathbb{Z}} = \varprojlim \mathbb{Z}/n\mathbb{Z}$ –  user53932 Jan 10 '13 at 14:01

You are right. Since $\hat{\mathbb{Z}}$ is flat over $\mathbb{Z}$, the natural map $H^i(X,\mathbb{Z}) \otimes \hat{\mathbb{Z}} \longrightarrow H^i(X,\hat{\mathbb{Z}})$ is an isomophism (of $\hat{\mathbb{Z}}$-modules).
If $M = \mathbb{Z}^r \oplus M_{t}$ is a finitely generated group (where $M_t$ is the torsion subgroup), then $\hat{M} := M \otimes \hat{\mathbb{Z}} \cong \hat{\mathbb{Z}}^r \oplus M_t$ (because $M_t \otimes \hat{\mathbb{Z}} = M_t$). The torsion subgroup of $\hat{M}$ as $\mathbb{Z}$-module (NOT as $\hat{\mathbb{Z}}$-module) is $M_t$. The rank can be recovered in the following way : let $p$ be any prime and denote $\hat{M}_p$ a pro-$p$-Sylow of $M \otimes \hat{\mathbb{Z}}$ (it is a pro-$p$-subgroup with quotient of 'profinite order' prime to $p$), then $r$ is the rank of $\hat{M}_p$ as $\mathbb{Z}_p$-module (the rank is well defined for modules over PID).


text:
# Change of measure discrete time

Suppose I have a random walk $X_{n+1} = X_n+A_n$ where $A_n$ is an iid sequence, $\mathsf EA_n = A>0$. How to construct a martingale measure for this case?

-

 what should I do if $A$ say $\mathcal N(1,1)$? – Ilya Jun 23 '11 at 17:41 For g, you could use an Hermite polynomial of random (independent) degree, applied to A-1. Use it to pushforward the law of A countably many times. Construct the limit of this compatible system.Finally apply your measurable mapping: Xn+1=Xn+An. X is a martingale. Btw is this homework?The question is useless because too vague: specifying probability space and filtration would help. – imateapot Jun 23 '11 at 18:54


text:
Last change on this file since 39:31a1a79019bb was 39:31a1a79019bb, checked in by Peter Kovacs <kpeter@…>, 10 years ago

Fully rework and extend the adaptors section

File size: 14.4 KB
Line
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19namespace lemon {
20/**
22
23In typical algorithms and applications related to graphs and networks,
24we usually encounter situations in which a specific alteration of a graph
25has to be considered.
26If some nodes or arcs have to be hidden (maybe temporarily) or the reverse
27oriented graph has to be used, then this is the case.
28However, actually modifing physical storage of the graph or
29making a copy of the graph structure along with the required maps
30could be rather expensive (in time or in memory usage) compared to the
31operations that should be performed on the altered graph.
32In such cases, the LEMON \e graph \e adaptor \e classes could be used.
33
34
35[SEC]sec_reverse_digraph[SEC] Reverse Oriented Digraph
36
37Let us suppose that we have an instance \c g of a directed graph type, say
38\ref ListDigraph and an algorithm
39\code
40  template <typename Digraph>
41  int algorithm(const Digraph&);
42\endcode
43is needed to run on the reverse oriented digraph.
44In this situation, a certain adaptor class
45\code
46  template <typename Digraph>
47  class ReverseDigraph;
48\endcode
49can be used.
50
51The graph adaptors are special classes that serve for considering other graph
52structures in different ways. They can be used exactly the same as "real"
53graphs, i.e. they conform to the \ref graph_concepts "graph concepts", thus all
54generic algorithms can be performed on them. However, the adaptor classes
55cannot be used alone but only in conjunction with actual graph representations.
56They do not alter the physical graph storage, they just give another view of it.
57When the methods of the adaptors are called, they use the underlying
58graph structures and their operations, thus these classes have only negligible
59memory usage and do not perform sophisticated algorithmic actions.
60
61This technique yields convenient tools that help writing compact and elegant
62code, and makes it possible to easily implement complex algorithms based on
63well tested standard components.
64
65For solving the problem introduced above, we could use the follwing code.
66
67\code
68  ListDigraph g;
69  ReverseDigraph<ListDigraph> rg(g);
70  int result = algorithm(rg);
71\endcode
72
73Note that the original digraph \c g remains untouched during the whole
74procedure.
75
76LEMON also provides simple "creator functions" for the adaptor
77classes to make their usage even simpler.
78For example, \ref reverseDigraph() returns an instance of \ref ReverseDigraph,
79thus the above code can be written like this.
80
81\code
82  ListDigraph g;
83  int result = algorithm(reverseDigraph(g));
84\endcode
85
86Another essential feature of the adaptors is that their \c Node and \c Arc
87types convert to the original item types.
88Therefore, the maps of the original graph can be used in connection with
90
91In the following code, Dijksta's algorithm is run on the reverse oriented
92graph but using the original node and arc maps.
93
94\code
95  ListDigraph g;
96  ListDigraph::ArcMap length(g);
97  ListDigraph::NodeMap dist(g);
98
100  // add more nodes and arcs
101
102  dijkstra(reverseDigraph(g), length).distMap(dist).run(s);
103\endcode
104
105In the above examples, we used \ref ReverseDigraph in such a way that the
106underlying digraph was not changed. However, the adaptor class can even be
107used for modifying the original graph structure.
108It allows adding and deleting arcs or nodes, and these operations are carried
109out by calling suitable functions of the underlying digraph (if it supports
110them).
111
112For this, \ref ReverseDigraph "ReverseDigraph<GR>" has a constructor of the
113following form.
114\code
115  ReverseDigraph(GR& gr);
116\endcode
117
118This means that in a situation, when the modification of the original graph
119has to be avoided (e.g. it is given as a const reference), then the adaptor
120class has to be instantiated with \c GR set to be \c const type
121(e.g. <tt>GR = const %ListDigraph</tt>), as in the following example.
122
123\code
124int algorithm1(const ListDigraph& g) {
125  ReverseDigraph<const ListDigraph> rg(g);
126  return algorithm2(rg);
127}
128\endcode
129
130\note Modification capabilities are not supported for all adaptors.
131E.g. for \ref ResidualDigraph (see \ref sec_other_adaptors "later"),
132this makes no sense.
133
134As a more complex example, let us see how \ref ReverseDigraph can be used
135together with a graph search algorithm to decide whether a directed graph is
136strongly connected or not.
137We exploit the fact the a digraph is strongly connected if and only if
138for an arbitrarily selected node \c u, each other node is reachable from
139\c u (along a directed path) and \c u is reachable from each node.
140The latter condition is the same that each node is reachable from \c u
141in the reversed digraph.
142
143\code
144  template <typename Digraph>
145  bool stronglyConnected(const Digraph& g) {
146    typedef typename Digraph::NodeIt NodeIt;
147    NodeIt u(g);
148    if (u == INVALID) return true;
149
150    // Run BFS on the original digraph
151    Bfs<Digraph> bfs(g);
152    bfs.run(u);
153    for (NodeIt n(g); n != INVALID; ++n) {
154      if (!bfs.reached(n)) return false;
155    }
156
157    // Run BFS on the reverse oriented digraph
158    typedef ReverseDigraph<const Digraph> RDigraph;
159    RDigraph rg(g);
160    Bfs<RDigraph> rbfs(rg);
161    rbfs.run(u);
162    for (NodeIt n(g); n != INVALID; ++n) {
163      if (!rbfs.reached(n)) return false;
164    }
165
166    return true;
167  }
168\endcode
169
170Note that we have to use the adaptor with '<tt>const Digraph</tt>' type, since
171\c g is a \c const reference to the original graph structure.
172The \ref stronglyConnected() function provided in LEMON has a quite
173similar implementation.
174
175
177
178Another typical requirement is the use of certain subgraphs of a graph,
179or in other words, hiding nodes and/or arcs from a graph.
180LEMON provides several convenient adaptors for these purposes.
181
182\ref FilterArcs can be used when some arcs have to be hidden from a digraph.
183A \e filter \e map has to be given to the constructor, which assign \c bool
184values to the arcs specifying whether they have to be shown or not in the
185subgraph structure.
186Suppose we have a \ref ListDigraph structure \c g.
187Then we can construct a subgraph in which some arcs (\c a1, \c a2 etc.)
188are hidden as follows.
189
190\code
191  ListDigraph::ArcMap filter(g, true);
192  filter[a1] = false;
193  filter[a2] = false;
194  // ...
195  FilterArcs<ListDigraph> subgraph(g, filter);
196\endcode
197
198The following more complex code runs Dijkstra's algorithm on a digraph
199that is obtained from another digraph by hiding all arcs having negative
200lengths.
201
202\code
203  ListDigraph::ArcMap<int> length(g);
204  ListDigraph::NodeMap<int> dist(g);
205
206  dijkstra(filterArcs( g, lessMap(length, constMap<ListDigraph::Arc>(0)) ),
207           length).distMap(dist).run(s);
208\endcode
209
210Note the extensive use of map adaptors and creator functions, which makes
211the code really compact and elegant.
212
213\note Implicit maps and graphs (e.g. created using functions) can only be
214used with the function-type interfaces of the algorithms, since they store
215only references for the used structures.
216
217\ref FilterEdges can be used for hiding edges from an undirected graph (like
218\ref FilterArcs is used for digraphs). \ref FilterNodes serves for filtering
219nodes along with the incident arcs or edges in a directed or undirected graph.
220If both arcs/edges and nodes have to be hidden, then you could use
221\ref SubDigraph or \ref SubGraph adaptors.
222
223\code
224  ListGraph ug;
225  ListGraph::NodeMap<bool> node_filter(ug);
226  ListGraph::EdgeMap<bool> edge_filter(ug);
227
228  SubGraph<ListGraph> sg(ug, node_filter, edge_filter);
229\endcode
230
231As you see, we needed two filter maps in this case: one for the nodes and
232another for the edges. If a node is hidden, then all of its incident edges
233are also considered to be hidden independently of their own filter values.
234
235The subgraph adaptors also make it possible to modify the filter values
236even after the construction of the adaptor class, thus the corresponding
237graph items can be hidden or shown on the fly.
238The adaptors store references to the filter maps, thus the map values can be
239set directly and even by using the \c enable(), \c disable() and \c status()
240functions.
241
242\code
243  ListDigraph g;
247
248  ListDigraph::NodeMap<bool> filter(g, true);
249  FilterNodes<ListDigraph> subgraph(g, filter);
250  std::cout << countNodes(subgraph) << ", ";
251
252  filter[x] = false;
253  std::cout << countNodes(subgraph) << ", ";
254
255  subgraph.enable(x);
256  subgraph.disable(y);
257  subgraph.status(z, !subgraph.status(z));
258  std::cout << countNodes(subgraph) << std::endl;
259\endcode
260
261The above example prints out this line.
262\code
263  3, 2, 1
264\endcode
265
266Similarly to \ref ReverseDigraph, the subgraph adaptors also allow the
267modification of the underlying graph structures unless the graph template
268parameter is set to be \c const type.
269Moreover the item types of the original graphs and the subgraphs are
270convertible to each other.
271
272The iterators of the subgraph adaptors use the iterators of the original
273graph structures in such a way that each item with \c false filter value
274is skipped. If both the node and arc sets are filtered, then the arc iterators
275check for each arc the status of its end nodes in addition to its own assigned
276filter value. If the arc or one of its end nodes is hidden, then the arc
277is left out and the next arc is considered.
278(It is the same for edges in undirected graphs.)
279Therefore, the iterators of these adaptors are significantly slower than the
280original iterators.
281
282Using adaptors, these efficiency aspects should be kept in mind.
283For example, if rather complex algorithms have to be performed on a
284subgraph (e.g. the nodes and arcs need to be traversed several times),
285then it could worth copying the altered graph into an efficient
286structure (e.g. \ref StaticDigraph) and run the algorithm on it.
287Note that the adaptor classes can also be used for doing this easily,
288without having to copy the graph manually, as shown in the following
289example.
290
291\code
292  ListDigraph g;
293  ListDigraph::NodeMap<bool> filter_map(g);
294  // construct the graph and fill the filter map
295
296  {
297    StaticDigraph tmp_graph;
298    ListDigraph::NodeMap<StaticDigraph::Node> node_ref(g);
299    digraphCopy(filterNodes(g, filter_map), tmp_graph)
300      .nodeRef(node_ref).run();
301
302    // use tmp_graph
303  }
304\endcode
305
306\note Using \ref ReverseDigraph could be as efficient as working with the
307original graph, but most of the adaptors cannot be so fast, of course.
308
309
311
312Two other practical adaptors are \ref Undirector and \ref Orienter.
313\ref Undirector makes an undirected graph from a digraph disregarding the
314orientations of the arcs. More precisely, an arc of the original digraph
315is considered as an edge (and two arcs, as well) in the adaptor.
316\ref Orienter can be used for the reverse alteration, it assigns a certain
317orientation to each edge of an undirected graph to form a directed graph.
318A \c bool edge map of the underlying graph must be given to the constructor
319of the class, which define the direction of the arcs in the created adaptor
320(with respect to the inherent orientation of the original edges).
321
322\code
323  ListGraph graph;
324  ListGraph::EdgeMap<bool> dir_map(graph, true);
325  Orienter<ListGraph> directed_graph(graph, dir_map);
326\endcode
327
328LEMON also provides some more complex adaptors, for
329instance, \ref SplitNodes, which can be used for splitting each node of a
330directed graph into an in-node and an out-node.
331Formally, the adaptor replaces each node u in the graph with two nodes,
332namely uin and uout. Each arc (u,v) of the original
333graph will correspond to an arc (uout,vin).
335for each node u of the original digraph.
336
337The aim of this class is to assign costs or capacities to the nodes when using
338algorithms which would otherwise consider arc costs or capacities only.
339For example, let us suppose that we have a digraph \c g with costs assigned to
340both the nodes and the arcs. Then Dijkstra's algorithm can be used in
341connection with \ref SplitNodes as follows.
342
343\code
344  typedef SplitNodes<ListDigraph> SplitGraph;
345  SplitGraph sg(g);
346  SplitGraph::CombinedArcMap<NodeCostMap, ArcCostMap>
347    combined_cost(node_cost, arc_cost);
348  SplitGraph::NodeMap<double> dist(sg);
349  dijkstra(sg, combined_cost).distMap(dist).run(sg.outNode(u));
350\endcode
351
352\note This problem can also be solved using map adaptors to create
353an implicit arc map that assigns for each arc the sum of its cost
354and the cost of its target node. This map can be used with the original
355graph more efficiently than using the above solution.
356
357Another nice application is the problem of finding disjoint paths in
358a digraph.
359The maximum number of \e edge \e disjoint paths from a source node to
360a sink node in a digraph can be easily computed using a maximum flow
361algorithm with all arc capacities set to 1.
362On the other hand, \e node \e disjoint paths cannot be found directly
363using a standard algorithm.
364However, \ref SplitNodes adaptor makes it really simple.
365If a maximum flow computation is performed on this adaptor, then the
366bottleneck of the flow (i.e. the minimum cut) will be formed by bind arcs,
367thus the found flow will correspond to the union of some node disjoint
368paths in terms of the original digraph.
369
370In flow, circulation and matching problems, the residual network is of
371particular importance, which is implemented in \ref ResidualDigraph.
372Combining this adaptor with various algorithms, a range of weighted and
373cardinality optimization methods can be implemented easily.
374
375To construct a residual network, a digraph structure, a flow map and a
376capacity map have to be given to the constructor of the adaptor as shown
377in the following code.
378
379\code
380  ListDigraph g;
381  ListDigraph::ArcMap<int> flow(g);
382  ListDigraph::ArcMap<int> capacity(g);
383
384  ResidualDigraph<ListDigraph> res_graph(g, capacity, flow);
385\endcode
386
387\note In fact, this class is implemented using two other adaptors:
388\ref Undirector and \ref FilterArcs.
389
390[TRAILER]
391*/
392}
Note: See TracBrowser for help on using the repository browser.


text:
| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

# Search the digital library catalog

 Query: search in TitleAuthorAbstractKeywordsiskanje_cistoBesediloYear of publishing ANDORAND NOT search in TitleAuthorAbstractKeywordsiskanje_cistoBesediloYear of publishing ANDORAND NOT search in TitleAuthorAbstractKeywordsiskanje_cistoBesediloYear of publishing ANDORAND NOT search in TitleAuthorAbstractKeywordsiskanje_cistoBesediloYear of publishing Work type: All work types Habilitation (m4) Specialist thesis (m3) High school thesis (m6) Bachelor work * (dip) Master disertations * (mag) Doctorate disertations * (dok) Research Data or Corpuses (data) * old and bologna study programme Language: All languagesSlovenianEnglishGermanCroatianSerbianAfrikaansAlbanianArabicArmenianAzerbaijaniBosnianBulgarianCatalanChineseCzechDanishDutchEstonianFinnishFrenchGeorgianGerman (Austria)GreekHungarianIrishItalianJapaneseKazakhLatinLatvianLithuanianMacedonianMalteseMontenegrinNorwegianPolishPortugueseRomanianRussianSerbian (cyrillic)Slavic languagesSlovakSpanishSwedishTurkishUkrainianMultilingualUndeterminedUnknown Search in: DKUM    EPF - Faculty of Business and Economics    FE - Faculty of Energy Technology    FERI - Faculty of Electrical Engineering and Computer Science    FF - Faculty of Arts    FGPA - Faculty of Civil Engineering, Transportation Engineering and Architecture    FKBV - Faculty of Agriculture and Life Sciences    FKKT - Faculty of Chemistry and Chemical Engineering    FL - Faculty of Logistic    FNM - Faculty of Natural Sciences and Mathematics    FOV - Faculty of Organizational Sciences in Kranj    FS - Faculty of Mechanical Engineering    FT - Faculty of Tourism    FVV - Faculty of Criminal Justice and Security    FZV - Faculty of Health Sciences    MF - Faculty of Medicine    PEF - Faculty of Education    PF - Faculty of Law    UKM - University of Maribor Library    UM - University of Maribor    UZUM - University of Maribor PressCOBISS    Faculty of Business and Economic, Maribor    Faculty of Agriculture and Life Sciences, Maribor    Faculty of Logistics, Celje, Krško    Faculty of Organizational Sciences, Kranj    Faculty of Criminal Justice and Security, Ljubljana    Faculty of Health Sciences    Library of Technical Faculties, Maribor    Faculty of Medicine, Maribor    Miklošič Library FPNM, Maribor    Faculty of Law, Maribor    University of Maribor Library Options: Show only hits with full text Reset

 1 - 8 / 81 1.Experimental Investigations of Flow and Mixing in Taylor-Couette Reactor using PIV and LIF MethodsAnna Racina, Matej Požarnik, Matthias Kind, 2005, original scientific articleAbstract: Modern laser-optical methods (Particle Image Velocimetry and Laser Induced Fluorescence) for flow characterization are implemented to study the mixing behavior in Taylor-Couette Reactor without axial flow. In this study, cylinders with a radius-ratio equal to 0.63 are taken into account, which results in a direct transition from laminar fluid flow regime to a turbulent one. During PIV measurements special attention is paid to the system settings at which the error vector fraction is minimized. Energy dissipation rate and the distribution of local micromixing times are calculated from PN data. The average dissipation rate has values in the order of magnitude of 1▫$^{-3}$▫- 1▫$0^{-1}$▫ W/kg depending on the rotation rate of inner cylinder. The corresponding micromixing times are from 50 down to 5 ms. For LIF experiments the calibration procedure and the image processing sequence are presented. LIF data are used to study macro- and mesomixing. Macromixing in axial direction is approximated using a one-parameter model of mixing (cascade of stirred vessels). The value of diffusion coefficient (3 1▫$0^{-5}$▫) m2/s) agrees well with values published in literature. The methodology of determining the segregation index and the local mesomixing times in the flow is introduced, followed by the presentation of selected results.Keywords: fluid mechanics, mixing, laser induced flourescence methodPublished: 01.06.2012; Views: 859; Downloads: 33 Link to full text 2.Weakly coupled analysis of a blade in multiphase mixing vesselMatej Vesenjak, Zoran Ren, Matjaž Hriberšek, 2004, short scientific articleAbstract: Two or more physical systems frequently interact with each other, where the independent solution of one system is impossible without a simultaneous solution of the others. An obvious coupled system is that of a dynamic fluid-structure interaction. š8đ In this paper a computational analysis of thefluid-structure interaction in a mixing vessel is presented. In mixing vessels the fluid can have a significant influence on the deformation of blades during mixing, depending on speed of mixing blades and fluid viscosity.For this purpose a computational weakly coupled analysis has been performed to determine the multiphase fluid influences on the mixing vessel structure. The multiphase fluid field in the mixing vessel was first analyzed with the computational fluid dynamics (CFD) code CFX. The results in the form of pressure were then applied to the blade model, which was the analysed with the structural code MSC.visualNastran forWindows, which is based on the finiteelement method (FEM).Keywords: fluid mechanics, solid mechanics, coupled problems, computational analysis, two-phase fluid, mixing blade, pressure distribution, finite volume method, finite element methodPublished: 01.06.2012; Views: 921; Downloads: 60 Link to full text 3.Estimation of solid solubilities in supercritical carbon dioxide: Peng-Robinson adjustable binary parameters in the near critical regionMojca Škerget, Zorka Novak-Pintarič, Željko Knez, Zdravko Kravanja, 2002, original scientific articleAbstract: The density dependence of the binary parameters of the Peng-Robinson equation of state in near the critical region was examined. Published solubility data of eight compounds in pure CO2 have been fitted to the Peng-Robinson equation in combination with one and two parameters van der Waals mixing rules and in combination with the three parameter density dependent mixing rule of Mohamed and Holder. A systematic study has been done to determine the influence of different terms in the mixing rules. In order to obtain density dependence, binary parameters were calculated for each isotherm at particular experimental point separately in the way to equalise experimental and calculated solubility data. The system was formulated as an equation-oriented model and solved by means of a nonlinear programming optimisation algorithm. For all compounds the binary interaction parameters thus obtained were found to vary strongly with pressure in the range from 75 bar to approximately 150 bar, i.e. near the critical end point (CEP) of the low temperature branch of the three phase solid-liquid-gas (SLG) curve. At higher pressures, the parameter is practically independent on pressure. In general, for the systems investigated, kij increases linearly with increasing density and reaches a constant value at higher densities in the range from 700 to 800 kg/m3, depending on the system under investigation.Keywords: solid liquid equilibria, equation of state, mixing rules, binary parameters, near critical region, nonlinear programming, thermodynamic model, supercritical fluids, CO2, solubilityPublished: 01.06.2012; Views: 1421; Downloads: 74 Link to full text 4.Influence of a random field on particle fractionation and solidification in liquid-crystal colloid mixturesVlad Popa-Nita, Paul van der Schoot, Samo Kralj, 2006, original scientific articleAbstract: The influence of a random-anisotropy (RA) type disorder on the phase separation of nematogen-colloid mixtures is studied theoretically by combiningthe phenomenological Landau-de Gennes, Carnahan-Starling, and hard-sphere crystal theories. We assume that the colloids enforce the RA disorder on the surrounding thermotropic liquid-crystal (LC) molecules. We adopt the Imry-Ma argument according to which the lower-temperature phase exhibits a domain-type pattern. The colloids impose a finite degree of orientational ordering even in the isotropic (paranematic) phase. In the ordered phase they give rise to a domain-type structure, resulting in the distorted nematic (speronematic) phase. The RA field opposes the phase separation tendency. With increasing disorder the difference between the paranematic and speronematic ordering decreases. Consequently there is a critical disorder, above which both phases become identical from the orientation point of view, but have different concentrations of colloids. We have also estimated another characteristic value of disorder above which the isotropic phase can exist only in a liquid state, the crystal phase being suppressed completely.Keywords: liquid crystals, transitions, segregation, mixing, random fields, solidification, complex fluidsPublished: 07.06.2012; Views: 757; Downloads: 59 Link to full text 5.Code-switchingNada Šabec, 2005, independent scientific component part or a chapter in a monographKeywords: sociolingvistika, preklapljanje, bilingvizem, izbira jezika, jezikovni stiki, izposojanje, sociolinguistics, code-switching, bilingualism, code-mixing, borrowing, structural constraints, language contacts, language choice, language attitudesPublished: 10.07.2015; Views: 688; Downloads: 35 Link to full text 6.Automated landmark points detection by using a mixture of approachesBožidar Potočnik, 2015, original scientific articleAbstract: This paper deals with the automated detection of a closed curvećs dominant points. We treat a curve as a 1-D function of the arc length. The problem of detecting dominant points is translated into seeking the extrema of the corresponding 1-D function. Three approaches for automated dominant points detection are presented: (1) an approach based on fitting polynomial, (2) an approach using 1-D computer registration and (3) an innovative approach based on a multi-resolution scheme, zero-crossing and hierarchical clustering. Afterwards, two methods are introduced based on the linearly and non-linearly mixing the results from the three approaches. We then mix the results in a mean-square error sense by using the linear and non-linear fittings, respectively. We experimentally demonstrate the problem of detecting 21 landmarks on 38 vole-teeth that by mixing, the detection accuracy is improved by up to 41.47 % with respect to the results for individual approaches, as applied within the mixture.Keywords: closed curve, dominant point, landmark, automated detection, mixing model fitting, vole-toothPublished: 10.07.2015; Views: 573; Downloads: 7 Link to full text 7.Measurement of D0–D‾0 mixing and search for CP violation in D0 → K+K−,π+π− decays with the full Belle data setMarko Starič, Jyoti Prakash Biswal, Marko Bračko, Boštjan Golob, Samo Korpar, Peter Križan, Tara Nanut, Rok Pestotnik, Marko Petrič, Eva Ribežl, Samo Stanič, Anže Zupanc, 2016, original scientific articleAbstract: We report an improved measurement of $D^0–{\overline{D}}^0$ mixing and a search for $CP$ violation in $D^0$ decays to $CP$ -even final states $K^+K^−$ and $\pi^+\pi^-$. The measurement is based on the final Belle data sample of $976 fb^{−1}$. The results are $y_CP=(1.11±0.22±0.09)%$ and $A_Γ=(−0.03±0.20±0.07)%$, where the first uncertainty is statistical and the second is systematic.Keywords: charm mesons, mixing, CP violationPublished: 17.07.2017; Views: 343; Downloads: 202 Full text (577,27 KB)This document has many files! More... 8.First model-independent Dalitz analysis of $B^0 \to D^0K^{\ast 0}$, $D\to K_S^0\pi ^+\pi ^-$ decayK. Negishi, Jyoti Prakash Biswal, Marko Bračko, Boštjan Golob, Samo Korpar, Peter Križan, Tara Nanut, Rok Pestotnik, Marko Petrič, Eva Ribežl, Samo Stanič, Marko Starič, Luka Šantelj, Anže Zupanc, 2016, original scientific articleAbstract: We report a measurement of the amplitude ratio $r_S$ of $B^0 \to D^0K^{\ast 0}$ and $B^0 \to \bar {D^0}K^{\ast 0}$ decays with a Dalitz analysis of $D\to K_S^0\pi ^+\pi ^-$ decays, for the first time using a model-independent method. We set an upper limit $r_S < 0.87$ at the 68% confidence level, using the full data sample of $711\,{\rm fb}^{-1}$ corresponding to $772\times 10^6$ $B\bar {B}$ pairs collected at the $\Upsilon (4S)$ resonance with the Belle detector at the KEKB $e^+e^-$ collider. This result is obtained from observables $x_- = +0.4 ^{+1.0 +0.0}_{-0.6 -0.1} \pm 0.0$, $y_- = -0.6 ^{+0.8 +0.1}_{-1.0 -0.0} \pm 0.1$, $x_+ = +0.1 ^{+0.7 +0.0}_{-0.4 -0.1} \pm 0.1$, and $y_+ = +0.3 ^{+0.5 +0.0}_{-0.8 -0.1} \pm 0.1$, where $x_\pm = r_S \cos (\delta _S \pm \phi _3)$, $y_\pm = r_S \sin (\delta _S \pm \phi _3)$, and $\phi _3\ (\delta _S)$ is the weak (strong) phase difference between $B^0 \to D^0K^{\ast 0}$ and $B^0 \to \bar {D^0}K^{\ast 0}$.Keywords: CO2, CO3, Cabibbo-Kobayashi-Maskawa quark-mixing matrix, CP violation, experimental particle physicsPublished: 21.07.2017; Views: 370; Downloads: 65 Full text (555,01 KB)This document has many files! More...
Search done in 0.11 sec.


text:
Recombination currents in a solar cell

Recombination occurs spatially throughout the solar cell in varying magnitudes. The total recombination within the device can be thought of as the sum of each individual recombination component, which are distinguished by the location at which the recombination occurs. The thermal recombination current J0 is one such conceptualisation of the electron and hole recombination which can be used to quantify regional recombination components [1].   For a typical aluminium back surface field (Al-BSF) solar cell, the common recombination components are:

1. J0e – recombination which occurs in the emitter.
2. J0b – Recombination which occurs in the base or undiffused bulk of the solar cell.
3. J0bsf – recombination which occurs in the diffused back surface field of the device.

These recombination currents are depicted schematically in Figure 1 below.

Figure 1: Schematic illustration of the recombination processes in a standard aluminum back surface field silicon solar cell.

When researching and designing optimised solar cells, it is often imperative to identify the individual loss mechanisms within the device to, for instance, assess the effect of process variations or simulate device performance. The recombination in the diffused region can dominate a device’s performance and therefore the measurement of the emitter recombination by the extraction of the emitter saturation current density J0e is commonly performed using photoconductance measurements. In this procedure, a symmetrically passivated and diffused sample is fabricated with ideally identical process conditions to the actual devices of interest. For  symmetrically passivated and diffused sample, provided that the sample is in high injection, the effective lifetime is written as [2]:

$\frac{1}{\tau_{eff}}=\left(\ \frac{1}{\tau_{intrinsic}}+\frac{1}{\tau_{SRH}}\right)+J_{0e}\frac{2\left(N_b+\mathrm{\Delta n}\right)}{qWn_i^2}$, (1)

where Nb is the dopant concentration in the bulk, W is the width of the sample, ni is the intrinsic carrier concentration, Δn is the excess carrier density and Nb is the doping level in the bulk. Assuming that τSRH is independent of Δn, differentiating with respect to Δn yields the form,

$J_{0e}=\frac{1}{2}qn_i^2W\frac{d}{d\mathrm{\Delta n}}\left(\frac{1}{\tau_{eff}}-\frac{1}{\tau_{intrinsic}}-\frac{1}{\tau_{SRH}}\right)$,  (2)

which enables the extraction of J0 from the linear portion of the slope of 1/τeff1/τintrinsic vs. Δn. The bracketed term in the RHS of Eq. 2.57 is often referred to as the corrected lifetime, τcorr, and accounts for Auger recombination in the bulk. The 1/τSRH component accounts for SRH processes in the bulk, and in the case of high lifetime material (such as Float-zone silicon) is often assumed to be negligible. This method is commonly referred to as the “Kane-Swanson method”, and is a simple, quick and powerful method for the extraction of J0. For symmetrically diffused and/or passivated samples, J0 is analogous to J0e or J0s respectively, provided that in the latter case the sample is under strong inversion or accumulation. In the original 1985 paper, Kane and Swanson outlined key assumptions affecting the accuracy of this method;

• Assumed uniform excess carrier density in the bulk, which allows the average generation rate in the bulk to be approximated as a uniform generation rate in the sample. This is not strictly correct due to finite carrier mobility within the sample. Kane and Swanson recommend reducing the sample width and minimising the surface recombination velocity to minimise this effect.
• ni is constant, and therefore not taking into account Band gap narrowing effects with increasing injection.
• The sample must be in high injection, as in this region the bulk region has a linear dependence on injection level, whereas the surface has a quadratic dependence. As a rule of thumb, Δnmin > 10Nb was suggested.
• The sample must not be limited by Auger or SRH recombination in the bulk in high injection; the bulk lifetime is constant.
• The diffused region is electrically “invisible” and contributes negligibly to the conductance measurement.

A good analogy is to look at a solar cell as a leaking bucket where the water level represents the open circuit voltage and the holes in the bucket are the various recombination processes. This is shown schematically in the animation below.

[1] Cuevas, A., The Recombination Parameter J0. Energy Procedia, 2014. 55: p. 53-62. Available: https://www.sciencedirect.com/science/article/pii/S1876610214012971

[2] Kane, D.E. and R.M. Swanson. Measurement of the Emitter Saturation Current by a Contactless Photoconductivity Decay Method. in 18th IEEE Photovoltaic Specialists Conference. 1985. IEEE. Available: https://www.researchgate.net/publication/279691285_Measurement_of_the_Emitter_
Saturation_Current_by_a_Contactless_Photoconductivity_Decay_Method


text:
# For a compact logic, strong completeness follows from weak completeness

I have heard it said from reputable sources that one of the differences between a compact and a non-compact logic is that in a compact logic, strong completeness follows from weak completeness. However, I have not been able to prove this myself. Can anyone help me prove this?

For clarity's sake, here are some definitions.

Definition 1 A logic $\mathcal{L}$ is compact if for any $\Phi \subseteq \mathcal{L}$, whenever $\Phi' \models \varphi$ for some $\varphi \in \mathcal L$ and for all finite $\Phi' \subseteq \Phi$, then also $\Phi \models \varphi$.

Definition 1 A logic $\mathcal L$ is compact if for any $\Phi \subseteq \mathcal L$, if every finite subset of $\Phi$ is satisfiable, then also $\Phi$ is satisfiable.

Definition 2 A logic $\mathcal{L}$ is weak-complete if for all $\varphi \in \mathcal L$ we have $\models \varphi$ implies $\vdash \varphi$.

Definition 3 A logic $\mathcal L$ is strong-complete if for all $\varphi \in \mathcal{L}$ and $\Phi \subseteq \mathcal L$ we have $\Phi \models \varphi$ implies $\Phi \vdash \varphi$.

I assume the idea is to get the hypotheses $\Phi$ to the right side of $\models$ and then use the weak completeness. However, I am not sure how to actually do this, or what to do from there.

• How about using this? If $\Phi' = \{\phi_1, ..., \phi_n\}$ and $\psi = \phi_1 \land ... \land \phi_n$, then $\Phi' \models \phi$ if and only if $\models \psi \to \phi$. – Levon Haykazyan May 4 '16 at 9:54
• I think that the statement of Definition 1 is not quite what you meant. Did you mean that, for all $\Phi \subseteq L$, if $\Phi' \vDash \phi$ for some finite $\Phi' \subseteq \Phi$ then $\Phi \vDash \phi$? I would imagine that compactness might be more useful if stated differently: if $\Phi \vDash \phi$ then there is some finite $\Phi' \subseteq \Phi$ with $\Phi' \vDash \phi$. – Carl Mummert May 4 '16 at 11:03
• @Carl Mummert No, the compactness definition is definitely right. It's a kind of limit property: if every finite subset of an infinite set proves $\varphi$, then the infinite set itself must also prove $\varphi$. – mrp May 4 '16 at 11:16
• @mrp: the problem is that if we do not have $\emptyset \vdash \phi$ then the axiom just stated has no bearing on $\phi$. In general, we can't expect that every finite subset of will prove $\phi$. Put another way, if every finite subset of $\Phi$ proves $\phi$ then $\emptyset$ proves $\phi$, so $\Phi$ proves $\phi$ by monotonicity. So, unless every monotonic logic is compact we need a different form of compactness. – Carl Mummert May 4 '16 at 11:18
• @mrp Your Definition 1 is not compactness! Compactness states that if $\Phi\models\varphi$, then there is some finite subset $\Phi'\subseteq \Phi$ such that $\Phi'\models \varphi$. Taking the contrapositive, we have that if $\Phi'\not\models \varphi$ for every finite subset $\Phi'\subseteq \Phi$, then $\Phi\not\models \varphi$. This is the same as your statement, but with $\not\models$ in place of $\models$ - an important distinction! – Alex Kruckman May 4 '16 at 21:02

You will need a few more properties of the logic, in addition to the ones stated. Perhaps the author you were reading included these properties as part of the definition of a "logic". Also, the form of compactness stated in the question is not the ideal one for this purpose.

Suppose that we replace compactness with the following:

• $\Phi \vDash \phi$ if and only if there is a finite $\Phi' \subseteq \Phi$ with $\Phi' \vDash \phi$

And suppose we assume the logic satisfies two more requirements:

1. A form of the deduction theorem: $\psi \vDash \phi$ if and only if $\vDash \psi \to \phi$, and $\psi \vdash \phi$ and and only if $\vdash \psi \to \phi$

2. A property of conjunction: if $\Psi$ is finite and $\psi$ is the conjunction of the axioms of $\Psi$ then $\Psi \vDash \phi$ if and only if $\psi \vDash \phi$, and $\Psi \vdash \phi$ if and only if $\psi \vdash \phi$.

Then we can prove that weak completeness implies strong completeness, following this outline:

• Suppose $\Phi \vDash \phi$
• By compactness, choose a finite $\Psi \subseteq \Phi$ with $\Psi \vDash \phi$
• Let $\psi$ be the conjunction of $\Psi$. Then $\psi \vDash \phi$ by requirement 2
• So $\vDash \psi \to \phi$ by requirement 1
• So $\vdash \psi \to \phi$ by weak completeness
• So $\psi \vdash \phi$ by requirement 1
• So $\Psi \vdash \phi$ by requirement 2
• So $\Phi \vdash \phi$ by compactness (this half of compactness is just the monotonicity of $\vdash$)

A counterexample

Here is a counterexample showing that the result does not work with the original version of compactness from the question. Begin with ordinary propositional logic with infinitely many propositional variables. For the deductive system, use any of the standard complete deductive systems for propositional logic.

For the semantics, first construct a collection $\mathcal{M}$ of models so that, for each sentence $\phi$ in the language, if $\phi$ is not a tautology then there is $M \in \mathcal{M}$ such that $M \not \vDash \phi$, but also each $M \in \mathcal{M}$ has infinitely many variables that evaluate to T and infinitely many that evaluate to F. This is possible because each formula only mentions finitely many variables, and we just need to choose one model $M$ for each non-tautology.

To finish our logic, we define $\Phi \vDash_\mathcal{M} \psi$ to mean that every model in our collection $\mathcal{M}$ which satisfies $\Phi$ also satisfies $\psi$.

1. This logic has weak completeness. We have that a sentence $\phi$ is a tautology if and only if $\vdash \phi$, because we use the usual deductive system. But we defined $\mathcal{M}$ so that $\phi$ is true in every model of $\mathcal{M}$ if and only if $\phi$ is a tautology, and hence our logic has the property that $\vDash_\mathcal{M} \phi$ if and only if $\vdash \phi$.

2. This logic has compactness in the form of the question. Assume that every finite subset $\Phi'$ of a set of axioms $\Phi$ satisfies $\Phi' \vDash_\mathcal{M} \phi$. Then in particular $\emptyset \vDash_\mathcal{M} \phi$, so $\phi$ holds in every model in $\mathcal{M}$, so $\Phi \vDash_\mathcal{M} \phi$.

3. This logic also satisfies requirements 1 and 2 above. This is because, essentially, we chose enough models in $\mathcal{M}$ to ensure that the only logically valid sentences are the tautologies.

4. This logic does not satisfy strong completeness. Let $\Phi$ be the set of axioms which states that every propositional variable has the value T. Then $\Phi$ is not satisfiable in $\mathcal{M}$, so we have $\Phi \vDash_\mathcal{M} \bot$. But $\Phi$ is syntactically consistent, because we are using the normal deductive system, so $\Phi \not \vdash \bot$.

This kind of example is a standard way to get (the usual version of) compactness to fail: take a logic that does have soundness, completeness, and compactness, and then restrict the semantics to use some appropriate subset of the interpretations of the original logic.

• I definitely agree that we need some properties to hold, such as the deduction theorem; I should have mentioned this in my question. This seems interesting and much like the kind of proof I had imagined, but it is not the definition of compactness I had in mind. – mrp May 4 '16 at 11:25
• I added a counterexample showing that the notion of compactness from the question is not sufficient. – Carl Mummert May 4 '16 at 12:03


text:
Archives

On zero-sum magic graphs and their null sets
by Ebrahim Salehi

Vol. 3 No. 2 (2008) P.255~P.264

ABSTRACT

For any $h \in N$, a graph $G = (V,E)$ is said to be $h$-magic if there exists a labeling $l : E(G) \to \mathbb{Z}_h$ - {0} such that the induced vertex labeling $l^+ : V(G) \to \mathbb{Z}_h$ defined by
$l^+(v) = \sum_{uv\in E(G)} l(uv)$
is a constant map. When this constant is 0 we call $G$ a zero-sum $h$-magic graph. The null set of $G$ is the set of all natural numbers $h \in \mathbb{N}$ for which $G$ admits a zero-sum $h$-magic labeling. A graph $G$ is said to be uniformly null if every magic labeling of $G$ induces zero sum. In this paper we will identify the null sets of the generalized theta graphs and introduce a class of uniformly null magic graphs.

KEYWORDS
magic, non-magic, zero-sum, null set, uniformly null

MATHEMATICAL SUBJECT CLASSIFICATION 2010
Primary: 05C78

MILESTONES


text:
# Which software to buy ?

#### WeeG

##### TS Contributor
Hi Guys,

someone asked me today which statistical software should he buy for his work. the field of work is biostatistics, there will be a need for complicated models. the work might also include some data mining, resampling, and more. the other software he already uses is matlab. the software he want to buy should complete.

I was thinking about Stata along with Stat/transfer (because he can also use R which is free). any other suggestions ?

you can suggest SAS, STATA, JMP or STATISTICA

#### SE_Lazic

##### New Member
I prefer JMP to Statistica. JMP is interactive and allows you to think in terms of models. Statistica requires too many mouse clicks to do even simple analyses, and leads to "what is the right test" type of thinking rather than "how can I best model the data" type of thinking. I can't comment on SAS or Stata.

But why pay for stats software!? If your friend is familiar with matlab, R will be an easy transition. The playwith package (http://code.google.com/p/playwith/) and ggobi (http://www.ggobi.org/) can be used for interactive graphics. What more do you need

#### bugman

##### Super Moderator
Wee G

Id use R over everything, but of the packages you mentioned, I agree with SE_Lazic about JMP. Statisitica, IMO is aweful. I haven't used STATA.

#### Dason

In my opinion the only package that even should be considered other than R is SAS. I'd use R over SAS any day but SAS is really nice for certain things. (I guess if you're going to do SEM there might be other stats packages you would consider but that doesn't sound like the case).

May I ask why they feel they need something other than R?

#### WeeG

##### TS Contributor
I think they are looking for a package that will be easier to use, with less code writing. JMP sounds good, but isn't it necessary to learn the JMP script language to be able to use it's real power ? STATA is powerful and simple. STATISTICA was an option because of it's Data Mining features, but I guess R must have those, does it ?

##### New Member
I use Matlab for coding and Oxmetrics for quick point-and-click stuff. I think thats pretty optimal for my purposes.

#### Lazar

##### Phineas Packard
I think they are looking for a package that will be easier to use, with less code writing. JMP sounds good, but isn't it necessary to learn the JMP script language to be able to use it's real power ? STATA is powerful and simple. STATISTICA was an option because of it's Data Mining features, but I guess R must have those, does it ?
WeeG if they dont want to do coding have you considered deducer. Gives R an SPSS interface (i.e. point and click).

EDIT: Ah it depends on what you mean by complex analysis (sorry did not read that bit). Deducer might not be perfect for highly complex or analysis that are not typically (however, it is relatively easy to code new point and click menu options).

Last edited:

#### WeeG

##### TS Contributor
thank you everyone for your comments, I was doing some checkup of pricing on the Internet, and find something that might change the picture. The price of SAS is MUCH higher than the other packages. STATA is extremely cheaper (including STAT/TRANSFER). For even cheaper price I can get SYSTAT 13...what do you think about that ? I heard good reviews about it.

#### duskstar

##### New Member
I use Stata, SAS and R myself though am mainly a Stata user. I've never personally had a use for STAT transfer, if I ever need to move something into R I just export it as a csv file and then take it into R, though I suspect that might be an issue with larger datasets.

I dont have SAS at home anymore because of issues installing it on Vista home (my university gave us all a version to use at home, but I could never get it to work.)

I suppose a lot of it is personally preference. Each package has its advantages, but if its only basic stats you want, you might just want to look at which has the most understandable code for that person.

In my experiences:

Stata - Easy to use, can use "point and click" (though I never have). I use Stata, my manager uses SAS (hence why I know a bit of SAS).

SAS - Expensive. But, definitely superior with handling large datasets. I would say I think SAS is better for writing macros than Statas option to write programs.

R - Can't really go wrong if its free. The code is a bit different to get used too, but one you do, its okay to use.

I'm afraid I've never heard of SYSTAT.

#### WeeG

##### TS Contributor
thanks.

I suppose that my dilemma exist because I know that SAS is relatively powerful and flexible. On the other hand, STATA is also powerful in compare to other packages, and it's much cheaper. The question is, in case I got for STATA, if I'll need something very complicated, will R be able to handle anything that SAS does ? If the answer for that one is yes, I see no reason for me to choose SAS, since I am more familiar with R and STATA....

SYSTAT is like SPSS in the way of very easy to use, but I like it, it's has many options, models and test, and the output is useful, for every model you get automatically the information criteria's and all that. I work a bit with the demo version, and it surprised me in a good way, it's not bad, not bad at all, and cheap (relatively, none of these packages is actually cheap)

#### duskstar

##### New Member
I suppose that my dilemma exist because I know that SAS is relatively powerful and flexible. On the other hand, STATA is also powerful in compare to other packages, and it's much cheaper. The question is, in case I got for STATA, if I'll need something very complicated, will R be able to handle anything that SAS does ? If the answer for that one is yes, I see no reason for me to choose SAS, since I am more familiar with R and STATA....
I personally haven't ever found anything I can do in SAS which I can't do in Stata or R. Sometimes it maybe a bit fiddly though, I have sometimes had to write twice as much code to make something run the same way as it does in SAS. Stata is superior in some areas (in my opinion) such as survival analysis. I'd be interested to hear if others have ever found something they can do in one program but not in another, I'm sure there will be somethings.

#### WeeG

##### TS Contributor
I suppose examples can be found on both ways, I would also like to know if there is anything. I once wanted to bring data to longitudinal form, with SAS it took an entire procedure and with STATA one line.

##### Ninja say what!?!
In my education and professional experience, I have and use R, SAS, Stata, and Stat transfer (from the list you've provided) quite a bit.

From what I've seen, R and SAS are predominantly the software used to analyze data. They are programming languages which make it really easy to handle data.

SAS (Cost = licensed at ~$1000 or so a year) has established itself as the software to use for large datasets. Most business professionals I have come across use SAS and its established itself among financial analysts. R (Cost = free) can also handle large datasets if you have plenty of memory. A disclaimer though is that R does not guarantee its algorithms, whereas SAS in a way does. That's why usually, you'll see grant writers propose SAS (or Stata) in their grant proposals rather than R. Stata (Cost = ~$800, though you have to pay to upgrade when new versions are released) I've never really liked because of the point and click feature, though it makes it really easy for people who don't consider themselves good programmers. It seems to be used a lot among epidemiologists.

Stat transfer to me is sort of a waste of money. Most datasets can be converted to CSV format (or some other alternative) by the person giving you the data. Thus, you can import it using the software you already have. Also, most stats software have started integrating other data formats into their own formats. For example, SAS v9.2 now allows you to import Stata data.

I'd strongly recommend R since to me it's just as good as SAS (given that you have enough memory) and it's free. If you need the algorithms to be guaranteed to work though, I'd go with SAS.

##### Ninja say what!?!
I suppose that my dilemma exist because I know that SAS is relatively powerful and flexible. On the other hand, STATA is also powerful in compare to other packages, and it's much cheaper. The question is, in case I got for STATA, if I'll need something very complicated, will R be able to handle anything that SAS does ? If the answer for that one is yes, I see no reason for me to choose SAS, since I am more familiar with R and STATA....
Yes, R can do most things that SAS can. It has the same flexibility as SAS (IMO) so I think you should go that route instead.

I suppose examples can be found on both ways, I would also like to know if there is anything. I once wanted to bring data to longitudinal form, with SAS it took an entire procedure and with STATA one line.
Keep in mind that with SAS, you can also do it in one line using the proc transpose. The extra options are only required if you want more flexibility or are using additional datasets simultaneously (which I don't think STATA allows you).

#### Dason

I think Link does a good summary of how I feel too. SAS really is the only alternative to R in my opinion and I'd recommend Enterprise Guide if you were going to go the SAS route - it does a little bit of point and click driven stuff to make your life easier but I mainly like it for the code completion and help with the options you can throw into a proc. SAS isn't cheap but compared to the other packages I think it's the only one worth anything.

If you really desire point and click for R you can get it for a few things (R commander and deducer and the like) but there isn't a canonical nice GUI for R that allows menu driven interaction. I'm not a fan of that so I don't really care. If what you really want is just a nice environment other than the command line to interact with R then I'll recommend RStudio - it's pretty awesome.

#### JenB

##### New Member
Hi. I work for StatSoft. To clarify, STATISTICA Data Miner provides three different user interfaces for data mining: (1) Individual Analyses, (2) Recipes, and (3) Workspaces.

1. Individual Analyses: If you already know which algorithm to use, individual analyses provide a variety of algorithm-specific options. Algorithms include trees, boosted trees, random forests for classification and regression problems, automated neural networks, k-nearest neighbors, support vector machines, various clustering methods, Kohonen networks, partial least squares, generalized linear models, association rules, sequence analysis, etc.
2. Recipes: Easy-to-use wizard-like user interface that can be used by novices. Default algorithms include trees, boosted trees, random forests, neural networks, and support vector machines. See YouTube Data Mining Recipes video.
3. Workspaces: Analytic workflows composed of multiple algorithms, which display as icons/nodes. Use one of the provided workspace templates or create your own. Since STATISTICA integrates with R, you can also create R nodes. See YouTube Data Miner Workspace video.

#### WeeG

##### TS Contributor
thanks for the info, may I ask you a couple of questions, since you work for StatSoft ?

1. I have tried to find what are the prices of the different packages. Sometimes it was easy to locate the info on the net (Stata, Systat), sometimes was harder but I managed to find it (SAS). I couldn't find the price of STATISTICA anywhere...in addition to that, I can't even use a 30 day trial of the software without registration. why is that and how do you think this way help you to attract new customers ?

2. I am looking for a package for Biostatistics, but will need during time to use a bit of data mining and a bit of Bayesian modelling. Can you convince me why should I choose STATISTICA (along with R which I'll use anyway), over SAS, STATA or SYSTAT ?

Thanks !!

P.S These questions don't come to hint anything about any software, I am honestly curious, and find it interesting, I am aware that people from other companies will say good things about their packages, but I don't know much about STATISTICA, so it can be informative !

#### trinker

##### ggplot2orBust
[R] has a steep learning curve but once you got it its flexibility and power make it well worth the time you spent learning the program.

#### JenB

##### New Member
Hi WeeG,

1. I have tried to find what are the prices of the different packages. Sometimes it was easy to locate the info on the net (Stata, Systat), sometimes was harder but I managed to find it (SAS). I couldn't find the price of STATISTICA anywhere...in addition to that, I can't even use a 30 day trial of the software without registration. why is that and how do you think this way help you to attract new customers ?
STATISTICA is scalable for different numbers of users, and we allow you to mix and match functionality. Our quote depends on what your site needs based on the needs and skills of individual users. Your local StatSoft sales office will help tailor a quote to your specific needs and that will ultimately save you money.

2. I am looking for a package for Biostatistics, but will need during time to use a bit of data mining and a bit of Bayesian modelling. Can you convince me why should I choose STATISTICA (along with R which I'll use anyway), over SAS, STATA or SYSTAT ?
Reasons to consider STATISTICA are:
* Quality and accuracy of model performance
* Variety of available algorithms
* Strong graphical visualization of models
* Ease of use
* Ability to handle very large data sets

Best regards,
Jen

#### gianmarco

##### TS Contributor
Hi!
I agree with JenB about STATISTICA.
Even though I got an old version (8) and use it for very basic needs (hypothesis tests, charts, corrspondence analysis), I find it very user-friendly and easy to use.

Regards,
Gm