2
$\begingroup$

The Hartley function, the main measure of Nonspecificity, is essentially based on the count of all possible states. However, while coding the Hartley, I realized that "possible" means all remaining state descriptions, regardless of whether they are reachable or not from all other states. Let me give an intuitive example of a situation where this might make a difference: ages ago my best friend and I got carried away playing the video game Gauntlet till 9 am and on occasion, we noticed that the maze generator would sometimes create an open cell that was completely walled in; sometimes the game would generate a monster within that would be permanently stuck there, for the lifetime of that maze. In some situations, it may be helpful to disqualify such unreachable states when quantifying information.

Are there variants of the Hartley function or other Nonspecificity measures that address this? Perhaps there's something in the field of Markov chains, which I'm even less familiar with? Then again, perhaps it would be difficult to determine the reachability of all states in advance without running into Traveling Salesmen-type problems. Moreover, it begs the question of which group of states takes precedence - is Group A reachable from B and C, or are B and C reachable from A? I suppose that means that we could derive separate Nonspecificity figures for each subgroup, which incidentally probably wouldn't obey the triangle inequality or exhibit symmetry. The Hartley Function would essentially act as an upper bound against any such measure. This is not a pressing problem at this moment; I'm just trying to do a thorough job of coding as many alternative information measures as I can, little by little in order to familiarize myself with the field, and see a niche here that I haven't seen filled yet. Of course, I'm an amateur whose still unfamiliar with these topics, so if such a measure exists I'd probably be ignorant of it. Thanks in advance for any input. :)

$\endgroup$
0
$\begingroup$

There do not appear to be any formal measures, at least any widely in use. It does seem to be standard practice in the realms of Markov Chains and Finite State Automata to snip out any unreachable states though. Some desultory academic papers that mention this at least in passing include those on the list below. Developing our own DIY information criterion would be straightforward, since all we would need to do is subtract the nonspecificity of the unreachable states we’ve removed from the total nonspecificity. The tricky part is determining the unreachable states in advance, which is an advanced topic in networking theory; the last item on the list is the only example I could find that discusses such algorithms at length.

• Cui, Jin, 2016, “Data Aggregation in Wireless Sensor Networks,” Phd. thesis defended at the Intitute National des Sciences Appliques, Lyon.

• Karatkevich, A. G., 2004, “Detection of the Unreachable States in FSM Networks,” pp. 47-54 in Proceedings of the International Conference CAD DD. .

• Ziebart, Brian D.; Bagnell, J. Andrew and Ey, Anind K., 2011, “Maximum Causal Entropy Correlated Equilibria for Markov Games,” pp. 207-214 in Proceedings of AAMAS '11 The 10th International Conference on Autonomous Agents and Multiagent Systems, Vol. 1. Taipei, May 2-6, 2011. International Foundation for Autonomous Agents and Multiagent Systems: Richland, South Carolina

• Alippi, Cesare; Fummi, Franco;Piuri, Vincenzo; Sami, Mariagiovanna and Sciuto, Donatella, 1998, “Testability Analysis and Behavioral Testing of the Hopfield Neural Paradigm,” pp. 507-511 in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, September, 1998. Vol. 6, No. 3.

• Oyama, Yuki; Hato, Eiji; Scarinci, Riccardo and Bierlaire, Michel, 2017, “Markov Assignment for a Pedestrian Activity-based Network Design Problem,” presented Sept. 12, 2017 at the 6th symposium of the European Association for Research in Transportation (hEART), Haifa, Israel.

• Case, Mike, 2009, “On Invariants to Characterize the State Space for Sequential Logic Synthesis and Formal Verification,” University of California at Berkeley Technical Report No. UCB/EECS-2009-46, released. April 2, 2009

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.