modeling

semiotics

Complexity And Other Software Metrics

Information Classification & Measurement (entropy, transinformation, manifest vs. latent vs. destroyed information, ...)
Taxonomy of Structural Software Metrics (size, length, complexity, cohesion, coupling)
Computational Complexity and Power Classes

[SuB] Norbert Bischof: Struktur und Bedeutung: Eine Einführung in die Systemtheorie; Verlag Hans Huber 1995.
[PBSEM] L C Briand, S Morasca, V R Basili: Property-Based Software Engineering Measurement; IEEE Transactions on sofware engineering; 22(1); Jan. 1996.

CHECK: A Data Model for Object-Oriented Design Metrics (1997)

Johann Eder, Gerti Kappel, Michael Schrefl: Coupling and Cohesion in Object-Oriented Systems (1992)

data coupling
stamp coupling: in a call more data is passed (eg a composite object), than necessary - a part would suffice
control coupling: caller determines other callee's logic or vice versa.
external coupling: communication through structured shared data space (shared objects?)
common coupling: communication through shared global unstructured data space
content coupling: external access to object's internal data

Information Classification & Measurement

The classification and measurement of information in (proximate) information theory is demonstrated in the following information system context [SuB 72ff]:

   x   +-------+   y
 ----->| y=x+z |------>
       +-------+
           ^
(A)      z |
           |

Two channels (A) and (B) with a 2-bit information source x (values 0,1,2,3) as input, an endpoint y (values 0,1,2,3,4 in (A), values 0,1,2,3 in (B)) as output, and a 1-bit noise signal z (values 0,1).

In (A), where the noise adds to the signal, no information is lost (cf. table below): All of the 2 bit information (entropy H(x)) of x is still contained in y (with 2 1/4 bit entropy H(y)). However, only 1 1/4 bit is still manifest (the transinformation T(x,y)), the remaining 3/4 bit has been turned into latent information (I_L(y)) by the noise. This part of the information cannot be attributed to either x or the noise. The latent information about x can be recovered if the noise signal is known (see below).

In (B), where the noise is multiplied onto the signal, 1 bit information is lost irreversibly (cf. table below), since a noise of 0 maps results in an output y of 0 for any signal x: Of the 2 bit information (H(x)) of x, 4/5 bit are manifest in y (T(x,y)), and 1/5 bit is latent (I_L(y)).

   x   +-------+   y
 ----->| y=x*z |------>
       +-------+
           ^
(B)      z |
           |

entropy of x = medium information content

signal equivocation = the receiver's uncertainty what the sender actually sent (``disturbed'' information)

3/4

24/20

H(y|x)

signal dissipation (the sender's uncertainty what the receiver will receive)

15/20

T(x,y)

signal transinformation = information of x manifest in y (``undisturbed'' information) = H(x) - H(x|y) = H(y) - H(y|x)

noise transinformation.

1/4

11/20

I_L(y)

latent information = information in y overlapping from x and z = H(y) - T(x,y) - T(z,y). The manifest information is T(x,y) + T(z,y)

3/4

4/20

information lost unrecoverably

   x   +-------+   y   +-------+   u
 ----->| y=x+z |------>| u=y-z |------>
       +-------+       +-------+
           ^               ^
         z |_______________|
           |

The channel extended by an information processor reading the channel's endpoint y and the noise z and ``calculating'' output u. The processor recovers the disturbed information, i.e., converts the information about x which was latent in y back to manifest information in u.

Information Organization

[MB4 272] «Some claim that information measures organization. The argument runs like this: a deterministic system is predicatable, so watching its behavior provides no information; on the other hand a probabilistic system is unpredicatbale, so whatever it does is surprising or informative. Hence, the more organized a system the more informative the observation of it. This argument contains several important mistakes. Firstly, the information function is not defined on a set of systems (or of states of a system) but on system-message pairs. ... Hence it cannot measure the degree of organization of a system nor any other intrinsic property of it. Secondly, ... [t]he predicate "predictable" is not defined on the set of systems but on the set of pairs . Thirdly, prediction must not be equated with deterministic prediction. If a system is stochastic ... then its behavior may be predicted statistically ... In this case we may able to predicat probabilities (of e.g. transitions) and a number of propties derived from them ... Forthly, a stochastic system ... is not chaotic: ... an atom is not chaotic like the top of my desk, over which no probability distribution can be defined.
In conclusion, information does not measure organization. ... What we do have are measures of efficieny ... Knowing that a system is highly (or fairly or poorly) efficient we can infer that it is well (or fairly or poorly) organized to attain a certain goal or to help us perform a certain task. But efficiency is an indicator of organization not a measure of it.»

Taxonomy of Structural Software Metrics

From [PBSEM]: A system S = (E,R) consists of elements E and relationships R, subset of E × E. Assume that S' = (E',R') and S'' = (E'',R'') are two subsystems of S, (E',E''

E and R',R''

R). A modular system S_M is a system S together with a set M of subsystems whose elements are partitions of E, i.e.,

(E_m,R_m)

M: e

E_m, and

(E_m,R_m), (E'_m,R'_m)

M: E_m

E'_m = ų . Then metrics can be classified as follows:

A size metrix is a function Size which is
1. non-negative.
2. null for empty systems.
3. additive for unconnected partitions S' and S'', i.e., Size(S) = Size(S') + Size(S'') where E = E'E'' and R', R''R, and E'E'' = ų (implying R'R'' = ų).
Examples of size metrixes: lines of code, number of statements/modules/procedures; Halstead's Length, occurences of operators/operands; unique operators/operands; Respose For a Class [Chidamber, Kemerer],
A length metrix is a function Length which is
1. non-negative.
2. null for empty systems.
3. maximizing for unconnected partitions S' and S'': Length(S) = max{ Length(S'), Length(S'')}
  where E = E'E'' and R = R'R'', and E'E'' = ų (implying R'R'' = ų).
4. antitone w.r.t. shortcuts, i.e., does not increase by adding relationships between elements which are already connected by an undirected path of relationships:
  Length((E,R{ (e,e') })) <= Length(S)
  where e,e'E' and subsystem S' = (E',R') is a connected components of S.
5. monotone w.r.t. establishing connections, i.e., does not decrease by adding relationships between elements that have not been connected before:
  Length((E,R{ (e',e'') })) >= Length(S)
  where e'E' and e''E'' and subsystems S' = (E',R') and S'' = (E'',R'') are separate connected components of S.
Examples of length metrixes: nesting depth, depth of inheritance hierarchy.
A (structural) complexity metrix is a function Complexity which is
1. non-negative.
2. null in the absence of relationships.
3. undirected, i.e., Complexity((E,R)) = Complexity((E,R^-1)).
4. additive for unconnected partitions:
  Complexity(S) = Complexity(S') + Complexity(S''),
  where E = E'E'' and R = R'R'', and E'E'' = ų (implying R'R'' = ų).
5. additive-monotone w.r.t. merging unrelated (but possibly overlapping) systems S' and S'':
  Complexity(S) >= Complexity(S') + Complexity(S'')
  where R'R'' = ų.
Examples of complexity metrixes: number of definition-use pairs [Oviedo] (data flow graph complexity); ``Cyclomatic Complexity'' [McCabe] with a minor adaption (control flow graph complexity); fan-in and fan-out measures [Henry, Kafura] (but not their combination to a information flow measure).
A cohesion metrix for (a subsystem of) a modular system is a function Cohesion which is
1. normalized, i.e., within an interval [0 .. Max]
2. null in the absence of intramodule relationships.
3. (maximizing-)antitone w.r.t. merging unrelated (but possibly overlapping) modules:
  Cohesion(((E,R),M'-{m',m''}{m'+m''})) <= Cohesion(((E,R),M'))
  Cohesion(m'+m'' in ((E,R),M'-{m',m''}{m'+m''})) <= max{ Cohesion(m' in ((E,R),M')), Cohesion(m'' in ((E,R),M')) }
  if m',m''M', and no relationships in R exist between the elements of m' and m''.
  m'+m'' is the subsystem combination: (E',R') + (E'',R'') = (E'E'',R'R'').
4. monotone w.r.t. adding intramodule relationships:
  Cohesion(((E,R''),M'')) >= Cohesion(((E,R'),M'))
  Cohesion(m'' in ((E,R''),M'')) >= Cohesion(m' in ((E,R'),M'))
  if (E_m, R'_m)=m'M', (E_m, R''_m)=m''M'' with R'_mR''_m and R' - R'_m = R'' - R''_m.
Examples of cohesion metrixes: ratios of cohesive interactions [Briand, Morasca, Basili]; functional cohesion measures [Bieman, Ott].
A outbound/inbound coupling metrix for (a subsystem of) a modular system is a function Coupling which is
1. non-negative.
2. null in the absence of outgoing/ingoing intermodule relationships.
3. additive/invariant w.r.t. merging unrelated (but possibly overlapping) modules:
  Coupling(((E,R),M'-{m',m''}{m'+m''})) = Coupling(((E,R),M'))
  Coupling(m'+m'' in ((E,R),M'-{m',m''}{m'+m''})) = Coupling(m' in ((E,R),M')) + Coupling(m'' in ((E,R),M'))
  if m',m''M', and no relationships in R exist between the elements of m' and m''.
4. (additive-)antitone w.r.t. merging modules:
  Coupling(((E,R),M'-{m',m''}{m'+m''})) <= Coupling(((E,R),M'))
  Coupling(m'+m'' in ((E,R),M'-{m',m''}{m'+m''})) <= Coupling(m' in ((E,R),M')) + Coupling(m'' in ((E,R),M'))
  if m',m''M'.
5. monotone w.r.t. adding intermodule relationships:
  Coupling(((E,R''),M'')) >= Coupling(((E,R'),M'))
  Coupling(m'' in ((E,R''),M'')) >= Coupling(m' in ((E,R'),M'))
  if (E_m, R'_m)=m'M', (E_m, R''_m)=m''M'', with m' leaving/entering relationships in R' ,' leaving/entering relationships in R'', and R' without relationships leading out/into m' = R'' without relationships leading out/into of m''
Examples of coupling metrixes: Coupling Between Object classes and Respose For a Class [Chidamber, Kemerer]; import coupling and export coupling [Briand, Morasca, Basili].

Computational Complexity and Power Classes

Computer science has developed a taxonomy of complexity (computational difficulty) of problems and power of problem solving systems.

In different ranges of complexity are the main working ground of some fields of computer science (of course, a field is not strictly limited to a fixed range). The background color in the table should given an approximate impression where a field's main area is:

The Chomsky-hierarchy (enumerable, CSL, CFL, REG) for grammars is based on the grammars' weak generative capacity, i.e., on the terminal strings they can produce [x]. Cf. strong generative capacity, i.e., the produceable parse trees [x].

Text colors: black for complexity/power classes, green for solvers, problems from [Hopcroft+Ullman] or from elsewhere
det = deterministic, ndet = nondeterministic, c.f. = context-free, LC = lambda-calculus
Main reference [Hopcroft, Ullman: Introduction to automata theory, languages and computation; 1979]
also [F Henglein, H Mairson: The Complexity of Type Inference for Higher-Order Typed Lambda Calculi; POPL'91]
also [N Immerman: Languages That Capture Complexity Classes; SIAM Journal of Computing 1987]
also [A Arratia-Quesada, S Chauhan, I Stewart: Hierarchies in classes of program schemes; Journal of Logic and Computation 1999]
also [I Stewart: Logical definability versus computational complexity: another equivalence]
Cf. the hierarchy at wikipedia and the huge list of complexity classes and results at the Complexity Zoo
Computable,
RE (recursively enumerable)
coRE, RE
a syntactic class: RE functions can be explicitly enumerated [zoo]
Turing- complete solvers:Turing machines; 2-stack machines; counter machines; RAM; recursive functions; while programs; Chomsky grammars

Decidable,
R (recursive) =REcoRE; PR [cf. Ackermann]
a semantic class: R functions cannot be explicitly enumerated [zoo]

PR (primitive recursive)
elementary
a syntactic class: PR functions can be explicitly enumerated
Elementary
relation to EXPSPACE? (union of DTIME(2ⁿ), DTIME(2^2ⁿ), DTIME(2^{2^2ⁿ}), etc.) EXP-
SPACE
EXP
EXP
[TIME]
=PSPACE?, P
PSPACE
=NPSPACE; includes NP and coNP
(solvable in polynomial space)
Buechi automata;
second order existential logic with transitive closure [Imm];
NPSA (NPS + arrays) [mentioned in Ste]
NP (includes RP, =RP?)
(solvable ndet'ly in polynomial time)
ESO (second order existential logic) [theorem by Fagin 74 - found in Imm]
·········
coNP
(=NP?, includes coRP, =coRP?)
Problem in NP and coNP: integer factorization [wiki]
NLIN (=NTIME(n)?) (solvable ndet'ly in linear time on RAM) [cf. page 12] NTIME(n) (solvable ndet'ly in linear time on TM) [cf. page 12] CFL (context-free)
(below NTIME(n) and CSL[cf. page 12], unknown rel. to NL; diagram in wiki shows CFL below NC)
stack machines ("pushdown automata" PDA), context-free grammars (CFG) non-regular CFL ...
RP (includes P, =P?, sub of coNP?)
Randomized Polynomial time
defined wrt. probabilistic TMs
eg. is-nonprime
·········
coRP
(=RP?, includes P, =P?)
eg. is-prime P (=NC?[wiki])
(solvable det'ly in polynomial time, "tractable problems")
least fixed point logic (first order logic with least fixed point primitive) [Imm];
path system logic [mentioned in Arr+] [less?] NSPS (NPS with stack) [Arr+] CSL (context- sensitive) = NSPACE(n), ie. solvable ndet'ly in linear space [Kur64]
primitive recursive functions (equiv. to loop); loop programs; context- sensitive grammars (CSG) REG (regular)
=DSPACE(O(1)) ie. constant space, =NSPACE(O(1))
finite automata (DFA=NFA),
regular expressions,
monadic ESO[cf]
DSPACE(n)
(solvable det'dly in linear space) L (solvable det'ly in logarithmic space)
NL =coNL
(solvable ndet'ly in logarithmic space)
transitive closure logic (first order logic with special transitive closure primitive)[Imm];
NPS program schemes [Arr+]
NC Nick's Class
(includes NL)
(solvable in (log n)^c time on n^k parallel processors, eg. parallel-RAM = decidable by uniform Boolean circuits with polylogarithmic depth and a polynomial number of gates) NL-complete (hardest in NL): GAP - reachability in directed graph [by Savitch 73 - found in Imm]
(n log n)-space, etc, ...
P-complete (hardest in P, "probably not parallelizable" / "probably inherently sequential") · [complete or maybe simpler?] type inference for the simply-typed (first-order) LC
[by Wand 87 - found in Hen+]
· evaluating a propositional formula for given values
· emptiness of CFGs' languages
· CFG membership [wiki]
CVP - Circuit Value Problem: calculate output of given gate in given circuit for given inputs [wiki]
· linear programming [wiki]
· game of life [wiki]
· LZ78 compression [wiki]
NP-complete (hardest in NP, "probably intractable")
·········
coNP-complete (hardest in coNP) SAT - satisfyability of unquantified formula = evaluation of existentially quantified formula
Vertex Cover; Hamilton Circuit; Integer Linear Programming; Chromatic Number; TSP (traveling salesman); Exact Cover; Knapsack; Partition (of integer lists); Tetris, Minesweeper
·········
·is a structural subtyping entailed by a set of subtyping constraints
for simple types over latices of base types? [Hen+]
PSPACE-complete (hardest in PSPACE) known to be disjoint from NC; maybe subset of P or NP? ·type inference in the presence of subtyping over ground & function types
in a simplified form of the ML_< type system
[A Frey: Satisfying Subtype Inequalities in Polynomial Space; 1997]
QBF - evaluation of quantified Boolean formulas
(alternating exist, forall - the typical minmax game scenario cf)
L_cs - word-problem for CSLs

EXPTIME-complete · best move in Chess or Go on an n × n board [wiki]
EXPSPACE-complete (hardest problems solvable in exponential space): L_rex - does a regular expressions with exponentiation denote all strings?
· two regular expressions with star represent different languages? [wiki]
harder than any problem ndet'ly solvable in exponential time: · is an untyped term typable in the second order polymorphic LC (aka F₂)? [Hen+]
· the theory of reals with addition
non-elementary time: · Is an untyped term typable in F_omega? [Hen+]
· Is the normal of two lambda-terms typable in first-order typed LC the same?
[by Statman 79 - found in Hen+]
· Evaluation of formula with quantific. over (higher-order) Booleans functions
found in [Hen+]
non-primitive recursive: · the Ackermann function
semi-decidable (RE-complete):
· The Halting Problem is the canonical RE-complete problem [zoo] - determining, in F_<'s type system, whether one type is subtype of another
[B Pierce: Bounded quantification is undecidable; POPL'92]
L_u - pairs of TM encoding and accepted word
PCP - Post's Correspondence Problem
· ambiguity of CFGs, inherent ambiguity of CFLs
· CFG accepts everything,
· intersection of the languages of two CFGs is empty / is c.f.
· inverse of CFG's language is c.f.
· CFG's language is regular
non-computable - cf. hypercomputation:
TMs with oracles, and some forms of Quantum computers, ...
Arithmetic hierarchy: The halting problem for _n sits in _n+1 L_d - the diagonal language of TM encodings
L_e, L_r, L_nr - emptiness / recursiveness / non-recursiveness of a TM's language
· TM accepts everything, accepts exactly one word, accepts a regular set

Cf. Design and Analysis of Algorithms with some complexity examples.

For some of the (shown and further) complexity classes it has not yet been proven whether they are in fact separate or only appear so. Especially, the possibility of ``P = NP'' is repeatedly considered, and there are several results on the implication should it be true, but no proof put forward so far has been accepted by the scientific community (it would reclassify NP-complete problems from intractable to P). ``NP = NL?'' (ndet. polynomial time v. ndet. logarithmic space) is discussed here.

Further classes:

BPP (Bounded-error, Probabilistic, Polynomial time = solvable on probabilistic TM in polynomial time with error probability <1/2 = "feasible for computer with genuine random-numbers" [zoo]):
PP > BPP = coBPP > RP. BPP > NP? BPP < NP?
PSPACE > BPP > P [from diagram]
BQP (Bounded-error, Quantum, Polynomial time = solvable on quantum computer in polynomial time with error probability <1/2 = "feasible for quantum computers"[zoo]):
NP > BQP > P [from diagram].
PP > BQP > BPP [zoo]
Examples by [wiki]: Integer factorization (see Shor's algorithm), discrete log, simulation of quantum systems (see universal quantum computer). Examples by zoo]: the factoring and discrete logarithm problems [Sho97], the hidden Legendre symbol problem [DHI02], the Pell's equation and principal ideal problems [Hal02], and some other problems not thought to be in BPP.
BPL (bounded propability, logspace), symmetric L, alternating L [c.f. Imm]
AP (alternating polynomial time) = PSPACE; NL < DSPACE[log² n] << PSPACE [cf.]
monadic NP monadic coNP (by Fagin) [cf. Arr+]
Ad linear time: « Although determinstic linear time is a frequently used notion in the theory of algorithms it still does not have a universally accepted formalization in terms of a complexity class. This is merely because what can be computed in deterministic linear time stronly depends on the computational model and ther representation of the input. »
Grandjean compared three measures DLINEAR < DLIN < DTIME(n) (det. linear time on, respectively, restricted RAM, less restricted RAM, or on TM), and corresponding nondet. measures. No language is known that is both NLIN and P, but not DLIN.
DTIME(n) << NTIME(n) < NLIN [from here]

One of the few problems that provably need more than polynomial run time is the truth decision algorithm for statements in Presburger arithmetic.

Ulf Schünemann 210601