Fundamenta Informaticae - Volume 131, issue 3-4

Authors: Grozea, Cristian | Popescu, Marius

Article Type: Research Article

Abstract: This note describes our experiments aiming to empirically test the ability of machine learning models to act as decision oracles for NP problems. Focusing on satisfiability testing problems, we have generated random 3-SAT instances and found out that the correct branch prediction accuracy reached levels in excess of 99%. The branching in a simple backtracking-based SAT solver has been reduced in more than 90% of the tested cases, and the average number of branching steps has reduced to between 1/5 and 1/3 of the one without the machine learning model. The percentage of SAT instances where the machine learned heuristic-enhanced …algorithm solved SAT in a single pass reached levels of 80-90%, depending on the set of features used. Show more

Keywords: ML, machine learning, satisfiability, SAT, NP, heuristics

DOI: 10.3233/FI-2014-1024

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 441-450, 2014

Authors: Krithivasan, Kamala | Păun, Gheorghe | Ramanujan, Ajeesh

Article Type: Research Article

Abstract: We introduce and briefly investigate P systems with controlled computations. First, P systems with label restricted transitions are considered (in each step, all rules used have either the same label, or, possibly, the empty label, λ), then P systems with the computations controlled by languages (as in context-free controlled grammars). The relationships between the families of sets of numbers computed by the various classes of controlled P systems are investigated, also comparing them with length sets of languages in Chomsky and Lindenmayer hierarchies (characterizations of the length sets of ET0L and of recursively enumerable languages are obtained in this framework). …A series of open problems and research topics are formulated. Show more

Keywords: Membrane computing, P system, control word, Chomsky language, Lindenmayer language

DOI: 10.3233/FI-2014-1025

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 451-464, 2014

Authors: Nicolescu, Radu | Gimel’farb, Georgy | Morris, John | Delmas, Patrice | Gong, Rui

Article Type: Research Article

Abstract: We propose a novel approach to justify and guide regularisation of an ill-posed one-dimensional global optimisation with multiple solutions using a massively parallel (P system) model of the solution space. Classical optimisation assumes a well-posed problem with a stable unique solution. Most of important practical problems are ill posed due to an unstable or non-unique global optimum and are regularised to get a unique best-suited solution. Whilst regularisation theory exists largely for unstable unique solutions, its recommendations are often routinely applied to inverse optical problems with essentially non-unique solutions, e.g. computer stereo vision or image segmentation, typically formulated in terms …of global energy minimisation. In these cases the recommended regularisation becomes purely heuristic and does not guarantee a unique solution. As a result, classical optimisation algorithms: dynamic programming (DP) and belief propagation (BP) – meet with difficulties. Our recent concurrent propagation (CP), leaning upon the P systems paradigm, extends DP and BP to always detect whether the problem is ill posed or not and store in the ill-posed case an entire space of solutions that yield the same global optimum. This suggests a radically new path to proper regularisation: select the best-suited unique solution by exploring statistical and structural features of this space. We propose a P systems based implementation of CP and set out as a case study an application of CP to the image matching problem in stereo vision. Show more

Keywords: concurrent propagation, ill-posed problems, regularisation, multiple solutions, stereo matching, P systems, membrane computing, parallel and distributed computing models, actor model

DOI: 10.3233/FI-2014-1026

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 465-483, 2014

Authors: Zimand, Marius

Article Type: Research Article

Abstract: We derive quantitative results regarding sets of n-bit strings that have different dependency or independency properties. Let C(x) be the Kolmogorov complexity of the string x. A string y has α dependency with a string x if C(y) − C(y | x) ≥ α. A set of strings {x1 , . . . , xt } is pairwise α-independent if for all i ≠ j, C(xi ) − C(xi | xj ) < α. A tuple of strings (x1 , . . . , xt ) is mutually α-independent if C(xπ(1) . . . xπ(t) ) > C(x1 …)+. . .+C(xt ) − α, for every permutation π of [t]. We show that: • For every n-bit string x with complexity C(x) ≥ α + 7 log n, the set of n-bit strings that have α dependency with x has size at least (1/poly(n))2n−α . In case α is computable from n and C(x) ≥ α + 12 log n, the size of the same set is at least (1/C)2n−α − poly(n)2α , for some positive constant C. • There exists a set of n-bit strings A of size poly(n)2α such that any n-bit string has α-dependency with some string in A. • If the set of n-bit strings {x1 , . . . , xt } is pairwise α-independent, then t ≤ poly(n)2α . This bound is tight within a poly(n) factor, because, for every n, there exists a set of n-bit strings {x1 , . . . , xt } that is pairwise α-dependent with t = (1/poly(n)) · 2α (for all α ≥ 5 log n). • If the tuple of n-bit strings (x1 , . . . , xt ) is mutually α-independent, then t ≤ poly(n)2α (for all α ≥ 7 log n + 6). Show more

DOI: 10.3233/FI-2014-1027

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 485-497, 2014

Article Type: Other

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 499-500, 2014