Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Distributional Learning of Some Nonlinear Tree Grammars

Clark A., Kobele G. M., Kanazawa M., Yoshinaka R.

Fundamenta Informaticae

2016

Vol. 146, nr 4

339--377

A key component of Clark and Yoshinaka’s distributional learning algorithms is the extraction of substructures and contexts contained in the input data. This problem often becomes intractable with nonlinear grammar formalisms due to the fact that more than polynomially many substructures and/or contexts may be contained in each object. Previous works on distributional learning of nonlinear grammars avoided this difficulty by restricting the substructures or contexts that are made available to the learner. In this paper, we identify two classes of nonlinear tree grammars for which the extraction of substructures and contexts can be performed in polynomial time, and which, consequently, admit successful distributional learning in its unmodified, original form.

State-efficient One-bit-communication Solutions for Some Classical Cellular Automata Problems

Umeo H., Michisaka K., Kamikawa N., Kanazawa M.

Fundamenta Informaticae

2007

Vol. 78, nr 3

449-465

We present several state-efficient implementations on 1-bit inter-cell communication cellular automata for some classical cellular automata problems. The 1-bit inter-cell communication cellular automaton model (CA1-bit) studied in this paper is a subclass of cellular automata (CA) whose inter-cell communication at one step is restricted to 1-bit. We study an early bird problem, a firing squad synchronization problem and an integer sequence generation problem, all of which are known as the classical, fundamental problems in cellular automata. Firstly, it is shown that there exists a 37-state CA1-bit that solves the early bird problem in twice real-time. Then, we give a two-dimensional CA1-bit which can synchronize any n ×n (n ^(3) 2) square and m×n (m, n ^(3) 2) rectangular arrays in 2n - 1 and m+n+max(m, n) steps, respectively. In addition, we propose a generalized linear-time synchronization algorithm that operates in m+n+max(r+s,m+n-r-s+2)+O(1) steps on two-dimensional rectangular arrays of size m ×n with the general located at an arbitrary position (r, s) in the array, where m, n ^(3) 2, 1 ? r ? m and 1 ? s ? n. The time complexities for the first two algorithms developed are one to two steps larger than optimum ones proposed for O(1)-bit conventional communication model. In the last, it is shown that there exists a 1-state CA1-bit that can generate in real-time a context-sensitive integer sequence such that {2n | n = 1, 2, 3, ... }.