Displaying 141 – 160 of 332

Showing per page

A semantic construction of two-ary integers

Gabriele Ricci (2005)

Discussiones Mathematicae - General Algebra and Applications

To binary trees, two-ary integers are what usual integers are to natural numbers, seen as unary trees. We can represent two-ary integers as binary trees too, yet with leaves labelled by binary words and with a structural restriction. In a sense, they are simpler than the binary trees, they relativize. Hence, contrary to the extensions known from Arithmetic and Algebra, this integer extension does not make the starting objects more complex. We use a semantic construction to get this extension. This...

A sharpening of the Parikh mapping

Alexandru Mateescu, Arto Salomaa, Kai Salomaa, Sheng Yu (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

In this paper we introduce a sharpening of the Parikh mapping and investigate its basic properties. The new mapping is based on square matrices of a certain form. The classical Parikh vector appears in such a matrix as the second diagonal. However, the matrix product gives more information about a word than the Parikh vector. We characterize the matrix products and establish also an interesting interconnection between mirror images of words and inverses of matrices.

A sharpening of the Parikh mapping

Alexandru Mateescu, Arto Salomaa, Kai Salomaa, Sheng Yu (2010)

RAIRO - Theoretical Informatics and Applications

In this paper we introduce a sharpening of the Parikh mapping and investigate its basic properties. The new mapping is based on square matrices of a certain form. The classical Parikh vector appears in such a matrix as the second diagonal. However, the matrix product gives more information about a word than the Parikh vector. We characterize the matrix products and establish also an interesting interconnection between mirror images of words and inverses of .

A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines

Viliam Geffert, Norbert Popély (2010)

RAIRO - Theoretical Informatics and Applications

We show that one-way Π2-alternating Turing machines cannot accept unary nonregular languages in o(log n) space. This holds for an accept mode of space complexity measure, defined as the worst cost of any accepting computation. This lower bound should be compared with the corresponding bound for one-way Σ2-alternating machines, that are able to accept unary nonregular languages in space O(log log n). Thus, Σ2-alternation is more powerful than Π2-alternation for space bounded one-way machines with...

Currently displaying 141 – 160 of 332