𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Complexity and hierarchy: A level rule

✍ Scribed by Gad Yagil


Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
515 KB
Volume
4
Category
Article
ISSN
1076-2787

No coin nor oath required. For personal study only.

✦ Synopsis


n this article, the connection between structural complexity and hierarchical organization is examined. The following quantitative rule, connecting complexities evaluated at different hierarchical levels, is offered:

C A/C is the complexity of an A-level structure evaluated in terms of its C-sublevel components. This level rule is used to evaluate the complexity of the insulin A-chain at two different levels. The complexity of the insulin chain at the C (atomic)-sublevel is derived from its complexity on the B (amino acid)-sublevel and the complexities of the j component amino acids in terms of their C-level elements. The result obtained is the same as that previously evaluated by a direct approach not using the level rule. It is proposed that this level rule is applicable to a wide range of actual and virtual hierarchical systems.


πŸ“œ SIMILAR VOLUMES


A hierarchy for nondeterministic time co
✍ Stephen A. Cook πŸ“‚ Article πŸ“… 1973 πŸ› Elsevier Science 🌐 English βš– 515 KB

We prove the following theorem in this paper: For any real numbers rl, r2, 1 ~ rl ~ r2, there is a set .4 of strings which has nondeterministic time complexity n\*2, but not nondeterministic time complexity n\*l. The computing devices are nondeterministic multitape Turing machines.

A descriptive complexity approach to the
✍ Yassine HachaΔ±̈chi πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 204 KB

This paper gives some new logical characterizations of the class of rudimentary languages in the scope of descriptive complexity. These characterizations are based on a logic introduced by Parigot and Pelz to characterize Petri Net languages, and generalized quantiΓΏers of comparison of cardinality.

Discovering multiple levels of a task hi
✍ Duncan Potts; Bernhard Hengst πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 273 KB

Task hierarchies can be used to decompose an intractable problem into smaller more manageable tasks. This paper examines an existing algorithm (HEXQ) that automatically discovers a task hierarchy through interaction with the environment. The initial performance of the algorithm can be limited becaus