Ready.


copycat82: An Explosion of Complexity.

VD78, Da80, and SARA, each had reduced verifier complexity/dimensionality through subnet reductions/abstractions. But the case of copycat82 is the vice versa.

copycat82, loses Petri net verifiability. A new verifier is needed to verify those vaguely-chopped macros (the "component"s) of copycat82, but to deal with such a vagueness, would explode the complexity - beyond the complexity-level of the original full net.


plagiarism to explosion

In representation, copycat82 is imitative of E-nets. That is the (explicit) structure of copycat82's plagiarism. Its (implicit) claims about its analysis, turn out to be imitative of VD78. That is, reachability-test of subnets separately, and without data.

E-nets did not exhaustively verify, and Macro E-nets, NN73, expand the full set of macros in a net, rather than attempt to verify separately. Da80 introduced E-net X-transition to Petri nets. This would let an exhaustive-verifier, too - e.g: with k-bounded locations, or loops. But this is interpreted abstraction. That is, the Da80 verifier does not neglect the data, it employs the X-transition to interpret it. Although copycat82 imitates VD78, the Da80'ian assumptions exist, too. The two of them cancel/clash each other, and it crashes copycat82.

To make copycat82 verifiable with reachability-test, we would have to remove all of the vagueness of copycat82, so that the VD78 verifier would suffice. But copycat82 does not present any methods to do that transformation. The replacement of input/output macros, with equivalent subnets (cf. SARA CFA), certainly does not suffice. The macro-hierarchy itself is problematic - with or without the problems of the input/output macros. Those input/output macro-gate implementations, although trivial, they contain their own problems, too, any way.

Whenever/if copycat82, ever so slightly, attempts to be any-different than VD78, all of its three attempts , turn out to compound the vagueness-problems (pile up in complexity), in three-levels: Bad, worse, and worst:






1. Multiple un-coordinated input/output paths

copycat82 does not (or, cannot) transform the macroful representation to the required single-entrance-single-exit structure of a Petri net non-primitive transition (as required by VD78, too). As such, the attempt of copycat82 is limited to the cases where the input, is already limited to a single entrance-point (and output is limited to a single exit point). It does not warn the readers, though. Even its own examples violate that necessity, and as a result, copycat82 could not possibly even represent its own examples. Let alone verifying them with a Petri net verifier.

In cases where, the macro-hierarchy examples include, multiple-phases (imitative of SARA SL socket-calls), and/or if there is not a unique-expression at the entrance (and/or, at the exit), the Petri net'ness is not achieved. With a SARA analogy, the confusion of copycat82 is an expectation to verify a SARA SL module (with multiple sockets), as if it were representable as equivalent to a control-node. That is exactly impossible.

The syntax of copycat82 input/output expressions imitate SARA control-logic expressions, whereas they obey the resolution-versus-transition split, imitative of E-nets and VD78. The crippledness of this, is the subject of the page about copycat82 plagiarism about resolution-procedures

For example, even a two-sided communication, with an intermediate interface-machine "macro," would explode in complexity, if that intermediate-macro was to be taken opaque, instead of replaced with the equivalent net. e.g: With n=12 input/output-locations (half-duplex) at each side, to correspond to 12 phases of communication, It would appear as n=12 input/output locations at both sides. This explodes the explorable paths, from a single-possibility (of a linear path) to an explosive 212 (two-to-the-power-of-twelve) possible paths in the reachability test (any combination of the output locations may get tokens).

Although it is a simple token-flow, with a single token input/output at each turn, a verifier to expect-any-configuration, may expect any of the (un-coordinated) paths to get tokens, at its exit.

And, because the tokens may not necessarily exit at the same time-instance, the before-after cases may even increase that complexity. You ponder the numbers, if you like.

In general, when multiple such opaque subnets/macros exit in a net, the input-locations would also expect to be enabled - any number of them, at any time.

The example is not an unusual case. A verifier must keep cautious. Therefore any subnet with an ambiguity, would necessitate extra resources. But, if this was a side-effect of a wasteful opacity, the subnet complexity is only to explode, as compared to the original full net.






2. Multiple-output-pulses per single-input

VD78 does not use data-relationships at its first-level. It is the second-level of analysis. This does not introduce any problems for it, because the control-graph (Petri net) does not assume any internal-structure with a transition/subnet. A well-formed VD78 subnet, is proper, and conservative. Therefore, the history of past-executions would not matter, and it may never reactivate itself, before it finishes.

Da80 studies interpreted-abstractions. Therefore, data is kept with the verifier, as an E-net X-transition refers to it. A Da80 subnet (X-transition) preserves the rule to single-pulse output, per single-pulse input. Even if data were to be neglected, the possibilities would remain as the original choice of X-transition, i.e: Pick any of the two possible output paths. This is easy to exhaustively verify - with or without data.

copycat82 is not proper. It does not keep data, either. Furthermore, it mentions a possibility of multiple-steps-of-output, even to the same location(s) (so-called, the "superscript" operator). It is trivial to state, but quite impossible to manage.

Once a copycat82 subnet is enabled, the verifier may expect it to output tokens, at any time. There would be no such thing as a "finished transition." How would the verifier guess it, when to consider that transition as finished?

As such, in a loop, a transition may appear as if started many times, but never completeable. This would appear so, whether or not, that particular transition really outputs multiple tokens.

That would let anywhere from single to infinite output pulses, per single input pulse, and it would not let the wise-neglect that was enjoyable by VD78, and others. We cannot neglect the overlap-of-timings of different subnets. Although copycat82 admits it, too, it does not do (or, discuss) anything further, about it. It is left as it is.

The problems go on. They do not stop there. Even the input/output macros of copycat82 contain not-proper examples. The input-"or" and -"xor" may get stuck, based on previous token-flow history, and "priority_++" may (non-deterministically) lose priority, thereby change its behavior, after the first pass through the high-priority path. When any of these input-macros is used within a subnet, to connect its (sub)subnets, that subnet is (almost?) necessarily not-proper. This complicates any example, if it uses those trivial-but-gotchaful macros. Although copycat82 does not consider this relevant to data, takes them non-deterministic (similar to SARA control-logic), the non-proper consequences of copycat82 /faultfull) implementations mean a preserved internal state, which means a dataful representation.

Although, a transformation of such internal behavior, to be represented as a control-subnet at entrance and/or exit, is possible, that is not what copycat82 publishes. The need is obvious, but the content is not there. There is no indicator that such an inside-out strategy would be any preferrable over SARA strong-reduction, or VD78 well-formed subnets, at all. It would only be a possible patch to copycat82 - even if awkward.

Such a possibility of blocked-subnets extends the range of output-possibilities, too. Now, a subnet, even when enabled, may possibly never send any tokens output. This means, a single-input pulse may lead to zero-to-infinite output-pulses.

A block, with sticky-activation, cannot be defined by a static table, only. The whole execution history may be implicated. Each re-activation may find a different behavior. cf. those standard but faulty/gotchaful i/o logic macros "or-input", "++-priority", and also the wishful usages of the "xor-input". The used examples include a request for monitor-functions. If a function call occurs at the same time as a function completion, the system deadlocks. What is the sense of that?

A net node/transition may input/output (at most) a single token per any input/output path(s), each time it is enabled, and it fires. This is true for Petri nets, E-nets, SARA, as well as, the Da80, and VD78 varieties. But this is not kept by copycat82. e.g: see its trivial, but chaotic "superscript" (multiple/repeated output) operator. (Does not provide the implementation, either. We may do it, as it is trivial, but to isolate the repetition-code from within a procedure-text is not necessarily trivial, if we would attempt to express it as a net.

When such a repeated output, is not converted to a net, that means the vague-structure of such a net-node/transition, must be considered by the verifier. That means, after it is enabled, a net-node may continue token-output even infinite times. The verifier must mark those nodes which were ever enabled, at all. Next, it expects a token-output from any of them, at any time.

To use a not-proper subnet within a subnet, may introduce strange consequences. If we would assume it as "verified," it would be a surprise to find out that, when the container subnet is placed in a circuit, it may deadlock. e.g: When multiple tokens enter, to get blocked at an "xor" within the sub-subnet. This problem exists in an example-figure of copycat82 itself. Therefore, with subnets, if VD78 well-formedness does not exist, a verifier must consider multiple-scenarios of token-input, at a variety of configuration-timings. A single marking, or two, would not do.






3. Do ADTs exist, at all?

The problem is even vaguer with the ADTs - the "abstract" data types (read it as "absurd," in copycat82's case). Such ADTs, if not totally non-existent (or, equivalently, confined within a node, never visible outside of it), would mean a token might appear at the output of a node/macro that had been never enabled, at all. Consider ADT restriction-specifications. For example, if there is a run-time exception, such as division-by-zero, what would occur? May a token jump/jerk to appear at some unconnected place, all at once?

Does the net already contain "exception-management" paths out of every node/macro which contains a division operation in it? If so, the ADT is not any extra, because the E-net procedures already manage the input/output to the node/transition/macro they reside with. As the alternative, if the ADT may transfer the token to another node, elsewhere, that means the token would appear at the output of that other node, although it was never at its input. When coupled with the potential-infinity of output, this means any token may appear anywhere, any time. Even a node that outputs a token, might have started so many others, through ADTs, too.






Conclusion: copycat82 is Un-credible
Complexity is Exploded, Instead of Reduced

There are many points, for such "another verifier" to take into consideration, although never discussed by copycat82. It assumes a Petri net verifier would suffice (after only the i/o macros at the entrance/exit get replaced, and even this is unrealistically simplified, ignoring the vagueness of the chopped macro entrance/exits e.g: separate-paths at entry/exit, and/or "socket calls"). It also assumes those macros to be verifiable separately - as VD78 does. (It does not cite VD78 as its source, though.) As we discussed, it is not Petri nets, any more. Here we discuss that, it is not feasible, either, when it is not Petri nets. i.e: There is no such thing as "copycat82 method" - except the faultiness. You have to find examples that are trivially representable by all three of the E-nets, SARA, and VD78, to make it workable with copycat82, at all.

With the sort of hairy-scary "component"s in copycat82, complexity cannot be assumed to be dealt away by just pushing it out of sight. It might be out of sight, but any verification tool worth its name, would still have to fully-recursively verify that, too. The layers cannot be assumed isolated. The naive-recursion (which is only a repeat-loop) suggested by copycat82 takes notice of no such inter-dependencies among (not between, but among) layers. (It does not care even the inter-dependencies between adjacent layers, beyond expanding the i/o logic macros, if that, but that is another story.)

Not every algorithm need be decomposable. The copycat82 introduces undeterminism and inhibitor arcs and deadlock potentials (through the declared behavior of the primitive(s)), at times, a single level may need to become quite large. In other words, that one-tool-for-all-problems (divide and conqueor) may not be applicable.


The story does not start there, either

On this page, we only discussed the immense complexity-explosion which would occur, if anybody attempted to verify the copycat82 "component"s without a transformation to make it equivalent to its prior art. This meant that, the attemt to reduce complexity, extremely exploded it. The story was awful even without any such attempts, though. In fact, copycat82 attempts to "solve" its inherent complexities. Let's mention inhibitor arcs, too.


inhibitor arcs

Two of copycat82 input-macros, "xor" and "priority_++" contain inhibitor arcs. It was known that this would increase the complexity-level of a Petri net, to Turing equivalence. This is mentioned in copycat82, too, but next, it assumes boundedness - with a single sentence, but that is Petri nets. Boundedness is built-in with E-nets semantics, and the whole E-nets primitives/etc. are built around that. (Only macros, within themselves, may be having some other bounded-capacity, instead of 1-boundedness.) Petri nets only notice that, in safety/boundedness analysis (markings). Any other suggestion of copycat82? What implementations? What specifications?


The story does not stop there, either

All of those complexities, compound with each other. That is not only immense-complexity to verify, but it is also essentially meaningless to a human, when such a vagueness is especially coupled with the graph-clutter, spread throughout many pages.




Forum: . . (Fair Menu . . . . . Fault Report? . . . . . Remedy for your case . . . . . Noticed Plagiarism?)

Referring#: 0.0.1
Last-Revised (text) on Aug. 20, 2004 . . . that was http://www.geocities.com/ferzenr/decalun.complexity.htm
Refreshed presentation/links (with their text), and 4 typoes-removed, on Nov. 30, 2004
mirror to mid80.net, on June 16, 2009
Written by: Ahmed Ferzan/Ferzen R Midyat-Zila (or, Earth)
Copyright (c) 2004, 2009 Ferzan Midyat. All rights reserved.
mirror