Wyniki wyszukiwania - BazTech

1

Typology emerges from simplicity in representations and learning

Lambert Dakotah, Rawski Jonathan, Heinz Jeffrey

Journal of Language Modelling

|

2021

|

Vol. 9, No. 1

151--194

EN

We derive well-understood and well-studied subregular classes of formal languages purely from the computational perspective of algorithmic learning problems. We parameterise the learning problem along dimensions of representation and inference strategy. Of special interest are those classes of languages whose learning algorithms are necessarily not prohibitively expensive in space and time, since learners are often exposed to adverse conditions and sparse data. Learned natural language patterns are expected to be most like the patterns in these classes, an expectation supported by previous typological and linguistic research in phonology. A second result is that the learning algorithms presented here are completely agnostic to choice of linguistic representation. In the case of the subregular classes, the results fall out from traditional model-theoretic treatments of words and strings. The same learning algorithms, however, can be applied to model-theoretic treatments of other linguistic representations such as syntactic trees or autosegmental graphs, which opens a useful direction for future research.

2

Parallel Algorithms for Minimal Nondeterministic Finite Automata Inference

Jastrzab Tomasz, Czech Zbigniew J., Wieczorek Wojciech

Fundamenta Informaticae

|

2021

|

Vol. 178, nr 3

203--227

EN

The goal of this paper is to develop the parallel algorithms that, on input of a learning sample, identify a regular language by means of a nondeterministic finite automaton (NFA). A sample is a pair of finite sets containing positive and negative examples. Given a sample, a minimal NFA that represents the target regular language is sought. We define the task of finding an NFA, which accepts all positive examples and rejects all negative ones, as a constraint satisfaction problem, and then propose the parallel algorithms to solve the problem. The results of comprehensive computational experiments on the variety of inference tasks are reported. The question of minimizing an NFA consistent with a learning sample is computationally hard.

3

Designing and Learning Substitutable Plane Graph Grammars

Eyraud R., Oates T., Janodet J.-C., Papadopoulos F.

Fundamenta Informaticae

|

2016

|

Vol. 146, nr 4

403--430

EN

Though graph grammars have been widely investigated for 40 years, few learning results exist for them. The main reasons come from complexity issues that are inherent when graphs, and a fortiori graph grammars, are considered. The picture is however different if one considers drawings of graphs, rather than the graphs themselves. For instance, it has recently been proved that the isomorphism and pattern searching problems could be solved in polynomial time for plane graphs, that is, planar embeddings of planar graphs. In this paper, we introduce the Plane Graph Grammars (PGG) and detail how they differ to usual graph grammar formalism’s while at the same time they share important properties with string context-free grammars. In particular, though exponential in the general case, we provide an appropriate restriction on languages that allows the parsing of a graph with a given PGG in polynomial time. We demonstrate that PGG are well-shaped for learning: we show how recent results on string grammars can be extended to PGG by providing a learning algorithm that identifies in the limit the class of substitutable plane graph languages. Our algorithm runs in polynomial time assuming the same restriction used for polynomial parsing, and the amount of data needed for convergence is comparable to the one required in the case of strings.

4

A Canonical Semi-Deterministic Transducer

Beros A. A., De la Higuera C.

Fundamenta Informaticae

|

2016

|

Vol. 146, nr 4

431--459

EN

We prove the existence of a canonical form for semi-deterministic transducers with sets of pairwise incomparable output strings. Based on this, we develop an algorithm which learns semi-deterministic transducers given access to translation queries. We also prove that there is no learning algorithm for semi-deterministic transducers that uses only domain knowledge.

5

Inductive Synthesis of Cover-Grammars with the Help of Ant Colony Optimization

Wieczorek W.

Foundations of Computing and Decision Sciences

|

2016

|

Vol. 41, No. 4

297--315

EN

A cover-grammar of a finite language is a context-free grammar that accepts all words in the language and possibly other words that are longer than any word in the language. In this paper, we describe an efficient algorithm aided by Ant Colony System that, for a given finite language, synthesizes (constructs) a small cover-grammar of the language. We also check its ability to solve a grammatical inference task through the series of experiments.

6

The design and implementation of the system supporting the control of industrial-like processes

Jurek J.

Foundations of Control and Management Sciences

|

2008

|

No. 9

51-66

EN

The software design and the implementation of an intelligent system supporting the control of industrial-like processes is discussed in the paper. The main tasks of such a system are on-line monitoring, analysis and recognition of process patterns (the results of the recognition are to be used to control the process), and self-learning activity, which enable the system automatic gathering new information about the process in order to recognise new process patterns. The system is based on the syntactic pattern recognition paradigm with the use of quasi-context sensitive string grammars. The design model of the system has been prepared accordingly to the object-oriented approach. In the paper we present the overview of the model and its implementation, and we discuss its advantages.

7

Real–valued GCS classifier system

Cielecki Ł., Unold O.

International Journal of Applied Mathematics and Computer Science

|

2007

|

Vol. 17, no 4

539-547

EN

Learning Classifier Systems (LCSs) have gained increasing interest in the genetic and evolutionary computation literature. Many real-world problems are not conveniently expressed using the ternary representation typically used by LCSs and for such problems an interval-based representation is preferable. A new model of LCSs is introduced to classify realvalued data. The approach applies the continous-valued context-free grammar-based system GCS. In order to handle data effectively, the terminal rules were replaced by the so-called environment probing rules. The rGCS model was tested on the checkerboard problem.

8

The Object-oriented Architecture of the Syntactic Pattern-recognition System Based on GDPLL(k) Grammars

Jurek J.

Schedae Informaticae

|

2004

|

Vol. 13

83-102

EN

The syntactic pattern recognition model based on GDPLL (k) grammars has been proposed [6, 13] as an efficient tool for inference support in diagnostic and control expert systems. In this paper we discuss the software engineering aspect of the syntactic pattern recognition (sub)system. The architecture of the system should allow to embed the system in real-time environments, accumulate knowledge about the environment, and flexible react to the changes in the environment. The object-oriented approach has been applied to design the system, and the Unified Modeling Language has been used for the specification of the software model. In the paper we presented the model and its practical applications.