Fundamenta Informaticae - Volume 122, issue 4

Authors: Daubner, Jakub | Toman, Eduard

Article Type: Research Article

Abstract: In the present paper we estimate the size of a neighbourhood of constant order in the interval graph of a random Boolean function. So far, no bound of this parameter has been known.

Keywords: random Boolean function, hypercube, interval graph, disjunctive normal form

DOI: 10.3233/FI-2013-790

Citation: Fundamenta Informaticae, vol. 122, no. 4, pp. 275-295, 2013

Authors: Graff, Daniel | Richling, Jan | Werner, Matthias

Article Type: Research Article

Abstract: Dealing with cyber-physical systems (CPS) puts a strong emphasis on the interaction between computing and non-computing elements. Since the physical world is characterized by being strongly distributed and concurrent, this is also reflected in the computational world making the design of such systems a challenging task. If a number of tasks shall be executed on a CPS which are bound to time and space, may have dependencies to other tasks and requires a specific amount of computing devices, a solution requires a four-dimensional space-time schedule which includes positioning of the devices resulting in an NP-hard problem. In this paper, we …address the problem of spatial-temporal group scheduling using Timed Petri nets. We use Timed Petri nets in order to model the spatial, temporal, ordered and concurrent character of our mobile, distributed system. Our model is based on a discrete topology in which devices can change their location by moving from cell to cell. Using the time property of Petri nets, we model movement in a heterogeneous terrain as well as task execution or access to other resources of the devices. Given the modeling, we show how to find an optimal schedule by translating the problem into a shortest path problem, which is solvable with the known method of dynamic programming. Show more

Keywords: Spatial-temporal group scheduling problems, scheduling, Timed Petri nets, cyber-physical systems

DOI: 10.3233/FI-2013-791

Citation: Fundamenta Informaticae, vol. 122, no. 4, pp. 297-313, 2013

Authors: Kuppusamy, Lakshmanan | Mahendran, Anand | Krithivasan, Kamala

Article Type: Research Article

Abstract: Contextual grammars are introduced by Solomon Marcus in 1969 based on the fundamental concept of descriptive linguistics of insertion of strings in given contexts. Internal contextual grammars are introduced by Păun and Nguyen in 1980. For contextual grammars several descriptional complexity measures and levels of ambiguity have been defined. In this paper, we analyze the trade-off between ambiguity and complexity of languages generated by internal contextual grammars. The notion of a pseudo inherently ambiguous language with respect to two complexity measures is introduced and investigated. These languages can be generated by unambiguous grammars which are minimal with respect to one …measure and ambiguous if they are minimal with respect to the other measure. An open problem from [15] is solved in this framework. Show more

Keywords: inherently ambiguous, unambiguous, descriptional complexity measures, internal contextual grammars

DOI: 10.3233/FI-2013-792

Citation: Fundamenta Informaticae, vol. 122, no. 4, pp. 315-326, 2013

Authors: Przybyła-Kasperek, Małgorzata | Wakulicz-Deja, Alicja

Article Type: Research Article

Abstract: The paper includes a discussion of issues related to the process of global decision-making on the basis of information stored in several local knowledge bases. The local knowledge bases contain information on the same subject, but are defined on different sets of conditional attributes that are not necessarily disjoint. A decision-making system, which uses a number of knowledge bases, makes global decisions on the basis of a set of conditional attributes specified for all of the local knowledge bases used. The paper contains a description of a multi-agent decision-making system with a hierarchical structure. Additionally, it briefly overviews methods of …inference that enable global decision-making in this system and that were proposed in our earlier works. The paper also describes the application of the conditional attributes reduction technique to local knowledge bases. Our main aim was to investigate the effect of attribute reduction on the efficiency of inference in such a system. For a measure of the efficiency of inference, we mean mainly an error rate of classification, for which a definition is given later in this paper. Therefore, our goal was to reduce the error rate of classification. Show more

Keywords: decision-making system, global decision, rough set, reduction of set of conditional attributes

DOI: 10.3233/FI-2013-793

Citation: Fundamenta Informaticae, vol. 122, no. 4, pp. 327-355, 2013

Authors: Tzitzikas, Yannis | Papadakos, Panagiotis

Article Type: Research Article

Abstract: Current proposals for preference-based information access seem to ignore that users should be acquainted with the information space and the available choices for describing effectively their preferences. Furthermore users rarely formulate complex (preference or plain) queries. The interaction paradigm of Faceted Dynamic Taxonomies (FDT) allows users to explore an information space and to restrict their focus without having to formulate queries. Instead the users can restrict their focus (object set, or set of choices in general) gradually through a simple set of actions, each corresponding to a more refined query (formulated on-the-fly) which can be enacted by a simple click. …In this paper we extend this interaction paradigm with actions that allow users to dynamically express their preferences. The proposed model supports progressive preference elicitation, inherited preferences and scope-based resolution of conflicts over single or multi-valued attributes with hierarchically organized values. Finally we elaborate on the algorithmic perspective and the applicability of the model over large information bases. Show more

DOI: 10.3233/FI-2013-794

Citation: Fundamenta Informaticae, vol. 122, no. 4, pp. 357-399, 2013

Authors: Woźna-Szcześniak, Bożena | Zbrzezny, Andrzej

Article Type: Research Article

Abstract: In the paper we propose a translation of the existential model checking problem for timed automata and properties expressible in MITL to the existential model checking problem for HLTL. Such a translation, for example, allows to adopt LTL bounded model checking method for verification of the MITL properties.

DOI: 10.3233/FI-2013-795

Citation: Fundamenta Informaticae, vol. 122, no. 4, pp. 401-420, 2013

Article Type: Other

Citation: Fundamenta Informaticae, vol. 122, no. 4, pp. 421-421, 2013