Fundamenta Informaticae - Volume 130, issue 3

Authors: Madejski, Grzegorz

Article Type: Research Article

Abstract: Permutation grammars are an extension of context-free grammars with rules having the same symbols on both sides but possibly in a different order. An example of a permutation rule of length 3 is ABC → CBA. If these non-context-free rules are of length at most n, then we say that permutation grammar is of order n and all such grammars generate a family of permutation languages Permn . In 2010 Nagy showed that there exists a language such that it cannot be generated by a grammar of order 2, but rules of length 3 are enough. In other words, a …strict inclusion $Perm_2 \subsetneq Perm_3$ was obtained. We extend this result proving that $Perm_{4n \minus 2} \subsetneq Perm_{4n \minus 1}$ for n ≥ 1. Show more

Keywords: Permutation grammar, interchange rule, infinite hierarchy, context-free grammars

DOI: 10.3233/FI-2014-992

Citation: Fundamenta Informaticae, vol. 130, no. 3, pp. 263-274, 2014

Authors: Motallebi, Hassan | Azgomi, Mohammad Abdollahi

Article Type: Research Article

Abstract: In this paper, we investigate some important aspects of a new formalism for modelling and verification of hybrid dynamic systems (HDS), which is called multisingular hybrid Petri nets (MSHPNs). This new hybrid formalism is aimed to bridge the gap between hybrid automata (HA) and hybrid Petri nets (HPNs) by equipping the HPN model with the capabilities of HA to control the execution and firing of timed transitions. Practically, MSHPNs can be considered as the counterpart with the same expressive power as multisingular hybrid automata (MSHA). In order to analyse MSHPN models, a speed-based partitioning technique has been introduced in which …the variable space is partitioned based on the balance of continuous places. In this paper, we formalize the notions of conflicts and conflict resolution and the challenging issue of speed computation. Then, we focus on considering a translation from a bounded MSHPN to a multisingular hybrid automaton that preserves the behavioural semantics of the original MSHPN in terms of weak timed bisimulation. The translation algorithm uses the speed-based partitioning method and obtains a speed-based partitioning hybrid automaton for a given bounded MSHPN. Model checking a timed property for an MSHPN amounts to model checking its equivalent property on the obtained speed-based partitioning hybrid automaton, thus MSHPN models can be analysed using the existing tools. The advantages of the proposed method are twofold: (1) hybrid systems can be described more succinctly and therefore more readably as MSHPNs, and (2) one can use the existing tools (like HYTECH) to analyse MSHPN models. Show more

Keywords: hybrid dynamic systems, multisingular hybrid Petri nets (MSHPNs), multisingular hybrid automata (MSHA), translation, speed-based partitioning hybrid automata

DOI: 10.3233/FI-2014-993

Citation: Fundamenta Informaticae, vol. 130, no. 3, pp. 275-315, 2014

Authors: Pal, Sankar K. | Kundu, Suman | Murthy, C.A.

Article Type: Research Article

Abstract: The paper addresses the problem of finding top k influential nodes in large scale directed social networks. We propose two new centrality measures, Diffusion Degree for independent cascade model of information diffusion and Maximum Influence Degree. Unlike other existing centrality measures, diffusion degree considers neighbors' contributions in addition to the degree of a node. The measure also works flawlessly with non uniform propagation probability distributions. On the other hand, Maximum Influence Degree provides the maximum theoretically possible influence (Upper Bound) for a node. Extensive experiments are performed with five different real life large scale directed social networks. With independent cascade …model, we perform experiments for both uniform and non uniform propagation probabilities. We use Diffusion Degree Heuristic (DiDH) and Maximum Influence Degree Heuristic (MIDH), to find the top k influential individuals. k seeds obtained through these for both the setups show superior influence compared to the seeds obtained by high degree heuristics, degree discount heuristics, different variants of set covering greedy algorithms and Prefix excluding Maximum Influence Arborescence (PMIA) algorithm. The superiority of the proposed method is also found to be statistically significant as per T-test. Show more

Keywords: Centrality Measure, Social Network, Influence Maximization, Independent Cascade Model, Statistical Significance

DOI: 10.3233/FI-2014-994

Citation: Fundamenta Informaticae, vol. 130, no. 3, pp. 317-342, 2014

Authors: Sakai, Hiroshi | Wu, Mao | Nakata, Michinori

Article Type: Research Article

Abstract: This paper discusses issues related to incomplete information databases and considers a logical framework for rule generation. In our approach, a rule is an implication satisfying specified constraints. The term incomplete information databases covers many types of inexact data, such as non-deterministic information, data with missing values, incomplete information or interval valued data. In the paper, we start by defining certain and possible rules based on non-deterministic information. We use their mathematical properties to solve computational problems related to rule generation. Then, we reconsider the NIS-Apriori algorithm which generates a given implication if and only if it is either a …certain rule or a possible rule satisfying the constraints. In this sense, NIS-Apriori is logically sound and complete. In this paper, we pay a special attention to soundness and completeness of the considered algorithmic framework, which is not necessarily obvious when switching from exact to inexact data sets. Moreover, we analyze different types of non-deterministic information corresponding to different types of the underlying attributes, i.e., value sets for qualitative attributes and intervals for quantitative attributes, and we discuss various approaches to construction of descriptors related to particular attributes within the rules' premises. An improved implementation of NIS-Apriori and some demonstrations of an experimental application of our approach to data sets taken from the UCI machine learning repository are also presented. Last but not least, we show simplified proofs of some of our theoretical results. Show more

Keywords: Association and decision rules, Incomplete and non-deterministic information, Set and interval valued data sets, Rough set approximations, Apriori algorithm extensions and implementation, Soundness and completeness

DOI: 10.3233/FI-2014-995

Citation: Fundamenta Informaticae, vol. 130, no. 3, pp. 343-376, 2014