Fundamenta Informaticae

We present a fragment of Propositional Dynamic Logic based on the Intuitionistic Propositional Logic. We show that this logic has the finite model property, and therefore, is frame-complete.

In this paper, we investigate a knowledge representation formalism in the context of fuzzy data tables. A possibilistic decision logic incorporating linguistic terms is proposed for representing and reasoning about knowledge in fuzzy data tables. Two applications based on the logic are described. The first is the extraction of fuzzy rules from general fuzzy data tables. In this application, the knowledge in the tables may be made explicit by the formulas of the logic or used implicitly in decision-making. The second is for the fuzzy quantization problem of precise data tables. It can be viewed as a special case of the first, however, due to some special properties of the problem, a polynomial time rule extraction process can be obtained. Finally, the relationship of the logic with some works for handling uncertain information in data tables is also discussed.

Research on improving the performance of feedforward neural networks has concentrated mostly on the optimal setting of initial weights and learning parameters, sophisticated optimization techniques, architecture optimization, and adaptive activation functions. An alternative approach is presented in this paper where the neural network dynamically selects training patterns from a candidate training set during training, using the network's current attained knowledge about the target concept. Sensitivity analysis of the neural network output with respect to small input perturbations is used to quantify the informativeness of candidate patterns. Only the most informative patterns, which are those patterns closest to decision boundaries, are selected for training. Experimental results show a significant reduction in the training set size, without negatively influencing generalization performance and convergence characteristics. This approach to selective learning is then compared to an alternative where informativeness is measured as the magnitude in prediction error.

A synchronized extension system is a 4-tuple G=(V,L_1,L_2,S), where V is an alphabet and L_1, L_2 and S are languages over V. Such systems generate languages extending L_1 by L_2 to the left or to the right, and synchronizing on words in S. In this note we consider the relationship between synchronized extension systems and regular canonical systems. We are able to give a simplified and generalized proof for the classical result concerning the regularity of the languages defined by regular canonical systems.

In this paper we initiate a study of polynomial-time reductions for some basic decision problems of rewrite systems. We then give a polynomial-time algorithm for the unique-normal-form property of ground systems for the first time. Next we prove undecidability of several problems for a fixed string rewriting system using our reductions. Finally, we prove the decidability of confluence for commutative semi-thue systems. The Confluence and Unique-normal-form property are shown Expspace-hard for commutative semi-thue systems. We also show that there is a family of string rewrite systems for which the word problem is trivially decidable but confluence is undecidable, and we show a linear equational theory with decidable word problem but undecidable linear equational matching problem.