Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars

Jeż A., Okhotin A.

Fundamenta Informaticae

2018

Vol. 162, nr 1

43--72

Unambiguous conjunctive grammars with 1 nonterminal symbol are shown to be strictly weaker than the grammars with 2 nonterminal symbols, which are in turn strictly weaker that the grammars with 3 or more nonterminal symbols. This hierarchy is established by considering grammars over a one-symbol alphabet, for which it is shown that 1-nonterminal grammars describe only regular languages, 2-nonterminal grammars describe some non-regular languages, but all of them are in a certain sense sparse, whereas 3-nonterminal grammars may describe some non-regular languages of non-zero density. It is also proved that one can test a 2-nonterminal grammar for equivalence with a regular language, whereas the equivalence between a pair of 2-nonterminal grammars is undecidable.

Univariate Equations Over Sets of Natural Numbers

Jeż A., Okhotin A.

Fundamenta Informaticae

2010

Vol. 104, nr 4

329-348

It is shown that equations of the form φ(X) = ψ(X), in which the unknown X is a set of natural numbers and φ, ψ use the operations of union, intersection and addition of sets S + T = {m + n | m ∈ S, n ∈T}, can simulate systems of equations φ(X1, . . . ,Xn) = φ(X1, . . . ,Xn) with 1 ≤ j ≤ l, in the sense that solutions of any such system are encoded in the solutions of the corresponding equation. This implies computational universality of least and greatest solutions of equations φ(X) = ψ(X), as well as undecidability of their basic decision problems. It is sufficient to use only singleton constants in the construction. All results equally apply to language equations over a one-letter alphabet Σ = {α}.