Wyniki wyszukiwania - BazTech

1

Mirror Images and Schemes for the Maximal Complexity of Nondeterminism

Salomaa A.

Fundamenta Informaticae

|

2012

|

Vol. 116, nr 1-4

237-249

EN

We present schemes of deterministic finite automata such that, for every nontrivial automaton A resulting from the scheme with n states, the state complexity of the mirror image of the language L(A) equals 2n. The construction leads to cases, where the increase in complexity is maximal in the transition from nondeterministic devices to deterministic ones. We also discuss the crucial importance of the size of the alphabet and present some open problems.

2

Subword Balance in Binary Words, Languages and Sequences

Salomaa A.

Fundamenta Informaticae

|

2007

|

Vol. 75, nr 1-4

4690482-4690482

EN

We investigate binary words and languages having a balanced structure of (scattered) subwords. We introduce a "difference function" D for binary words. For D=0, the resulting language is properly context-sensitive. Parikh matrices constitute a useful technical tool in the study, we investigate also the independence of their entries. The investigation is extended to concern w-words and periodicity. For the Fibonacci word, the D-values are in many ways connected with the Fibonacci numbers.

3

Secret Sharing Schemes with Nice Access Structures

Ding C., Salomaa A.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

51-63

EN

Secret sharing schemes, introduced by Blakley and Shamir independently in 1979, have a number of applications in security systems. One approach to the construction of secret sharing schemes is based on coding theory. In principle, every linear code can be used to construct secret sharing schemes. But only well structured linear codes give secret sharing schemes with nice access structures in the sense that every pair of participants plays the same role in the secret sharing. In this paper, we construct a class of good linear codes, and use them to obtain a class of secret sharing schemes with nice access structures.

4

On Some Problems of Mateescu Concerning Subword Occurrences

Ding C., Salomaa A.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

65-79

EN

The paper investigates inference based on quantities |w|u, the number of occurrences of a word u as a scattered subword of w. Parikh matrices recently introduced are useful tools for such investigations. We introduce and study universal languages for Parikh matrices. We also obtain results concerning the inference from numbers |w|u to w, as well as from certain entries of a Parikh matrix to other entries.

5

On the Injectivity of Parikh Matrix Mappings

Salomaa A.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

391-404

EN

We investigate the number of (scattered) subword occurrences and Parikh matrices, especially the case where the matrix determines the word uniquely. A condition introduced in this paper, called g-property, turns out to be a powerful tool for such unambiguous matrices. Interconnections with the general theory of subword histories are also pointed out.

6

Membrane computing with external output

Paun G., Rozenberg G., Salomaa A.

Fundamenta Informaticae

|

2000

|

Vol. 41, Nr 3

313-340

EN

A membrane computing system (also called P system) consists of computing cells which are organized hierarchically by the inclusion relation: cells may include cells, which again may include cells, etc. Each cell is enclosed by its membrane. Each cell is an independent computing agent with its own computing program, which produces objects. The interaction between cells consists of the exchange of objects through membranes. The output of a computation is a partially ordered set of objects which leave the system through its external membrane. The fundamental properties of computations in such P systems with external output are investigated. These include the computing power, normal forms, and basic decision problems.