Fundamenta Informaticae - Volume 145, issue 4

Authors: Bagchi, Susmit

Article Type: Research Article

Abstract: The schedulers residing in kernel of Operating Systems employ patterns of resource affinities of concurrent processes in order to make scheduling decisions. The scheduling decisions affect overall resource utilization in a system. Moreover, the resource affinity patterns of a process may not be possible to profile statically in all cases. This paper proposes a novel probabilistic estimation model and a classifier algorithm to queuing processes based on respective resource affinities. The proposed model follows probabilistic estimation using execution traces, which can be either online or statically profiled. The algorithm tracks the resource affinities of processes based on periodic estimation and …classifies the processes accordingly for scheduling. The effects of variations of estimation periods are investigated and fuzzy refinements are introduced. Experimental results indicate that the classifier algorithm successfully determines resource affinities of a set of processes online. However, the algorithm can determine inherent affinity pattern of a process in the presence of uniform distribution having enhanced IO frequency. Show more

Keywords: Kernel, probabilistic estimation, scheduler, CPU-bound, IO-bound, scheduling quanta, fuzzy logic

DOI: 10.3233/FI-2016-1369

Citation: Fundamenta Informaticae, vol. 145, no. 4, pp. 405-427, 2016

Authors: Hidders, Jan | Paredaens, Jan

Article Type: Research Article

Abstract: We discuss three well-known languages for querying and manipulating XML documents: XQuery, XPath and XSLT. They are considered to be the standard languages for processing XML documents. However, specifying their complete semantics in a formal way seems almost impossible. Indeed, an attempt by the W3C XML Query Working Group to do so for XQuery was ultimately abandoned. We introduce three sublanguages, called MiXPath, MiXQuery and MiXSLT, and describe their syntax and formal semantics. The syntax and semantics of these languages are chosen such that they are consistent with the ones given in the related W3C recommendations. As such this provides …a practical foundation for research and teaching of XML languages. For this purpose the sublanguages are chosen such that they contain the most crucial features, constructs and expressions of each of these three languages. Show more

Keywords: semistructured data, transformation languages, XML, XPath, XQuery, XSLT, formal semantics

DOI: 10.3233/FI-2016-1370

Citation: Fundamenta Informaticae, vol. 145, no. 4, pp. 429-470, 2016

Authors: Komarath, Balagopal | Sarma, Jayalal | Sunil, K.S.

Article Type: Research Article

Abstract: We initiate a complexity theoretic study of the language based graph reachability problem (L–REACH ) : Fix a language L. Given a graph whose edges are labelled with alphabet symbols of the language L and two special vertices s and t , test if there is path P from s to t in the graph such that the concatenation of the symbols seen from s to t in the path P forms a string in the language L. We study variants of this problem with different graph classes and different language classes and …obtain complexity theoretic characterizations for all of them. Our main results are the following: • Restricting the language using formal language theory we show that the complexity of L–REACH increases with the power of the formal language class. We show that there is a regular language for which the L–REACH is NL-complete even for undirected graphs. In the case of linear languages, the complexity of L–REACH does not go beyond the complexity of L itself. Further, there is a deterministic context-free language L for which L–DAG REACH is LogCFL-complete. • We use L–REACH as a lens to study structural complexity. In this direction we show that there is a language A in TC0 for which A–DAG REACH is NP-complete. Using this we show that P vs NP question is equivalent to P vs DAG REACH −1 (P)1 question. This leads to the intriguing possibility that by proving DAG REACH −1 (P) is contained in some subclass of P, we can prove an upward translation of separation of complexity classes. Note that we do not know a way to upward translate the separation of complexity classes. Restricting the language using formal language theory we show that the complexity of L–REACH increases with the power of the formal language class. We show that there is a regular language for which the L–REACH is NL-complete even for undirected graphs. In the case of linear languages, the complexity of L–REACH does not go beyond the complexity of L itself. Further, there is a deterministic context-free language L for which L–DAG REACH is LogCFL-complete. We use L–REACH as a lens to study structural complexity. In this direction we show that there is a language A in TC0 for which A–DAG REACH is NP-complete. Using this we show that P vs NP question is equivalent to P vs DAG REACH −1 (P)1 question. This leads to the intriguing possibility that by proving DAG REACH −1 (P) is contained in some subclass of P, we can prove an upward translation of separation of complexity classes. Note that we do not know a way to upward translate the separation of complexity classes. Show more

Keywords: L-reachability, CFL-reachability, structural complexity

DOI: 10.3233/FI-2016-1371

Citation: Fundamenta Informaticae, vol. 145, no. 4, pp. 471-483, 2016

Authors: Zhang, Zhiqiang | Wu, Tingfang | Pan, Linqiang

Article Type: Research Article

Abstract: Numerical P systems are a class of P systems inspired both from the structure of living cells and from economics. In this work, we further investigate the generative capacity of numerical P systems as language generators. The families of languages generated by non-enzymatic, by enzymatic, and by purely enzymatic (all programs are enzymatic) numerical P systems working in the sequential mode are compared with the language families in the Chomsky hierarchy. Especially, a characterization of recursively enumerable languages is obtained by using purely enzymatic numerical P systems working in the sequential mode.

Keywords: Formal Language, Computational Power, Register Machine, String Language, Numerical P System, Sequential

DOI: 10.3233/FI-2016-1372

Citation: Fundamenta Informaticae, vol. 145, no. 4, pp. 485-509, 2016

Article Type: Other

Citation: Fundamenta Informaticae, vol. 145, no. 4, pp. 511-512, 2016