Fundamenta Informaticae - Volume 92, issue 3

Authors: Foustoucos, Eugénie | Kalantzi, Labrini

Article Type: Research Article

Abstract: We model the monadic second-order logic (MSO) evaluation problem on finite colored trees in a purely database theoretic framework, based on the well-knownMSO-automata connection: we reduce the problem to an acyclic conjunctive query evaluation problem on the one hand and to a monadic datalog evaluation problem on the other hand. This approach offers the possibility to solve the MSO problem using optimized evaluation methods for relational algebra expressions and for datalog programs (such as Yannakakis algorithm …[27] and the rewriting method using resolutionbased filtering referred to as "magic sets" method in [3]): we use these methods for evaluating our queries and giving estimates of their complexity. This is the first time, to our knowledge, that a solution to the MSO evaluation problem related to relational algebra is given; furthermore, thanks to this reduction, we prove that the automata-based algorithm given in [8] constitutes a particular "instance" of Yannakakis algorithm. Besides the optimized database methods that we propose for solving the MSO evaluation problem, our results prove that MSO-definable queries over colored trees are datalog-definable; this result subsumes the corresponding result in [12] which states that unary MSO queries are monadic datalog-definable and it also subsumes the well-known result that any MSO-definable class of trees is monadic datalog-definable. Show more

Keywords: Monadic second-order logic (MSO) evaluation problem , MSO queries, tree automata, datalog queries, acyclic conjunctive queries, Yannakakis algorithm, datalog rewriting algorithms, definability

DOI: 10.3233/FI-2009-0072

Citation: Fundamenta Informaticae, vol. 92, no. 3, pp. 193-231, 2009

Authors: Hölscher, Karsten | Kreowski, Hans-Jörg | Kuske, Sabine

Article Type: Research Article

Abstract: In this paper, we introduce the notion of a community of autonomous units as a rulebased and graph-transformational device to model processes that run interactively but independently of each other in a common environment. The main components of an autonomous unit are a set of rules, a control condition, and a goal. Every autonomous unit transforms graphs by applying its rules so that the control condition is satisfied. If the goal is reached the resulting transformation …process is successful. A community contains a set of autonomous units, an initial environment specification, and an overall goal. In every transformation process of a community the autonomous units interact via their common environment. As an example, the game Ludo is modeled as a community of self-controlled players who interact on a common board. The emphasis of the presented approach is laid on the study of the formal semantics of a community as a whole and of each of its member units separately. In particular, a sequential as well as a parallel semantics is introduced, and communities with parallel semantics are compared with Petri nets, cellular automata, and multiagent systems. Show more

Keywords: Autonomous units, graph transformation, formal semantics

DOI: 10.3233/FI-2009-0073

Citation: Fundamenta Informaticae, vol. 92, no. 3, pp. 233-257, 2009

Authors: Moshkov, Mikhail Ju. | Piliszczuk, Marcin | Zielosko, Beata

Article Type: Research Article

Abstract: Partial association rules can be used for representation of knowledge, for inference in expert systems, for construction of classifiers, and for filling missing values of attributes. This paper is devoted to the study of approximate algorithms for minimization of partial association rule length. It is shown that under some natural assumptions on the class NP, a greedy algorithm is close to the best polynomial approximate algorithms for solving of this NP-hard problem. The paper contains various …bounds on precision of the greedy algorithm, bounds on minimal length of rules based on an information obtained during the greedy algorithm work, and results of theoretical and experimental study of association rules for the most part of binary information systems. Show more

Keywords: Rough sets, information systems, association rules, greedy algorithm

DOI: 10.3233/FI-2009-0074

Citation: Fundamenta Informaticae, vol. 92, no. 3, pp. 259-277, 2009

Authors: Sroka, Jacek | Hidders, Jan

Article Type: Research Article

Abstract: Workflow development and enactment workbenches are becoming a standard tool for conducting in silico experiments. Their main advantages are easy to operate user interfaces, specialized and expressive graphical workflow specification languages and integration with a huge number of bioinformatic services. A popular example of such a workbench is Taverna, which has many additional useful features like service discovery, storing intermediate results and tracking data provenance. We discuss a detailed formal semantics for Scufl - …the workflow definition language of the Taverna workbench. It has several interesting features that are notmet in other models including dynamic and transparent type coercion and implicit iteration, control edges, failure mechanisms, and incominglinks strategies. We study these features and investigate their usefulness separately as well as in combination, and discuss alternatives. The formal definition of such a detailed semantics not only allows to exactly understand what is being done in a given experiment, but is also the first step toward automatic correctness verification and allows the creation of auxiliary tools that would detect potential errors and suggest possible solutions to workflow creators, the same way as Integrated Development Environments aid modern programmers. A formal semantics is also essential for work on enactment optimization and in designing the means to effectively query workflow repositories. This paper is the first of two. It defines, explains and discusses fundamental notions for describing Scufl graphs and their semantics. Then, in the second part, we use these notions to define the semantics and show that our definition can be used to prove properties of Scufl graphs. Show more

Keywords: formal semantics, Scufl, workflows, Taverna workbench

DOI: 10.3233/FI-2009-0075

Citation: Fundamenta Informaticae, vol. 92, no. 3, pp. 279-299, 2009

Authors: Yinbin, Lei | Maokang, Luo

Article Type: Research Article

Abstract: In 1978, G. Plotkin [7] conjectured that for the three-element truthvalue dcpo T, if κ > ω then the function space [T^{κ} → T^{κ} ] is not a retract of T^{κ} . In this short paper, we constructively prove a stronger result that if κ > ω then the function space [T^{κ} → T^{κ} ] is not a retract of the Cartesian product of any family of finite …posets. Thus Plotkin's Conjecture is proved to be correct. Show more

Keywords: coherent domain, T^{κ}, product, retract

DOI: 10.3233/FI-2009-0076

Citation: Fundamenta Informaticae, vol. 92, no. 3, pp. 301-306, 2009