Fundamenta Informaticae - Volume 31, issue 2

Authors: Majorinc, Kazimir

Article Type: Research Article

Abstract: Van Gelder has described a few reasons for satisfiability testing without transformation of formulas into CNF and has developed an algorithm for this problem. We have introduced two possible improvements. First, we have used directed acyclic graphs for the representation of formula, instead of representation in the form of a tree or a string of characters. Second, we have allowed a limited introduction of new variables, again without transformation to CNF. In terms of a proof system, Van Gelder’s algorithm does not p-simulate system described here. Some generalizations of notions of propositional formula, satisfiability, etc. are introduced.

Keywords: non-clausal propositional satisfiability, Van Gelder's algorithm, splitting rule

DOI: 10.3233/FI-1997-31201

Citation: Fundamenta Informaticae, vol. 31, no. 2, pp. 107-116, 1997

Authors: Martín-Vide, Carlos

Article Type: Research Article

Abstract: Computation not only takes place in provoked contexts of scientific experimentation, but in natural circumstances too. We are going to approach computation in natural contexts. How the nature computes? Turing machines and Chomsky grammars are rewriting systems, and the same is true for Post, Thue, Markov, Lindenmayer and other classes of axiomatic systems. If, among the whole set of natural objects, we focus natural language description, we must say that major trends in contemporary linguistics look at syntax as a rewriting process. Is rewriting unavoidable in this case, does our mind work by rewriting, does the nature compute in this …way? We shall attempt to defend that the answer could be negative. The arguments will come from computability theory as well as from linguistics. First we'll formally explain the former ones, then informally the latter ones. With regard to computability theory arguments, we will see that, using the operation of adjoining, a large generative capacity is obtained. This is the case with contextual grammars. It has recently been proved that each recursively enumerable language is the quotient by a regular language of a language generated by a contextual grammar of a particular form. Thus, adjoining (paste) and quotient (cut) lead to computational universality. Recursively enumerable languages can also be characterized as the quotient by a regular language of a language generated by an insertion grammar. The same result is obtained if we take the splicing operation, a formal model of the DNA recombination. This is again a cut-and-paste operation. On the basis of the proof of this result, several further characterizations of recursively enumerable languages have been obtained. Computability theory, then, could be reconstructed without rewriting (and non-terminal symbols) and without any loss in power. Our first aim will be to show some formal aspects of such reconstruction. Later, we'll try to obtain some consequences for the future development of generative theory of natural language. Show more

Keywords: Mathematical Linguistics, Formal Language Theory, Theory of Computation

DOI: 10.3233/FI-1997-31202

Citation: Fundamenta Informaticae, vol. 31, no. 2, pp. 117-124, 1997

Authors: Matskin, Mihhail | Komorowski, Jan

Article Type: Research Article

Abstract: The notion of partial deduction known from logic programming is defined in the framework of Structural Synthesis of Programs (SSP). Partial deduction for computability statements in SSP is defined. Completeness and correctness of partial deduction in the framework of SSP are proven. Several tactics and stopping criteria are suggested.

Keywords: Partial deduction, program synthesis

DOI: 10.3233/FI-1997-31203

Citation: Fundamenta Informaticae, vol. 31, no. 2, pp. 125-144, 1997

Authors: Moshkov, Mikhail | Chikalov, Igor

Article Type: Research Article

Abstract: Upper and lower bounds on minimal average weighted depth and minimal average depth of decision trees over arbitrary information systems are considered. In proofs methods of test theory and rough set theory are used.

Keywords: Information system, decision tree, average weighted depth

DOI: 10.3233/FI-1997-31204

Citation: Fundamenta Informaticae, vol. 31, no. 2, pp. 145-156, 1997

Authors: Moshkov, Mikhail

Article Type: Research Article

Abstract: The paper is devoted to investigation of behavior of global Shannon functions which produce unimprovable upper bounds on time complexity of decision trees over arbitrary information systems.

Keywords: Information system, decision tree, time complexity

DOI: 10.3233/FI-1997-31205

Citation: Fundamenta Informaticae, vol. 31, no. 2, pp. 157-184, 1997

Authors: Păun, Andrei

Article Type: Research Article

Abstract: Several characterizations of recursively enumerable languages are given, using H systems with permitting contexts having splicing rules of small radius. Representations of context-free languages are also obtained in certain particular cases. These results improve previous related results which were recently published. Some open problems are also pointed out.

Keywords: DNA computing, Splicing, H systems, Chomsky hierarchy

DOI: 10.3233/FI-1997-31206

Citation: Fundamenta Informaticae, vol. 31, no. 2, pp. 185-193, 1997

Authors: Skordev, Dimiter

Article Type: Research Article

Abstract: The abstract approach proposed here encompasses both the detection of some periodic loops during the execution of Prolog programs and the detection of some periodic loops during recursive computations (an attempt to look at the loop detection problem for Prolog from an abstract point of view has been done previously in a paper by the same author published in 1993).

Keywords: Cyclic loop, loop detection, logic program, recursive computation

DOI: 10.3233/FI-1997-31207

Citation: Fundamenta Informaticae, vol. 31, no. 2, pp. 195-212, 1997