Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: unary languages

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.

On the Size of Unary Probabilistic and Nondeterministic Automata

Bianchi M.P., Mereghetti C., Palano B., Pighizzini G.

Fundamenta Informaticae

2011

Vol. 112, nr 2/3

119-135

We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa’s in the following sense: For any positive integer d, there exists a unary d-cyclic language such that any pfa accepting it requires d states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa’s which from one side do not match a known optimal state lower bound and, on the other side, they are smaller than nfa’s which, in turn, are smaller than deterministic automata.

Behaviours of Unary Quantum Automata

Bianchi M.P., Palano B.

Fundamenta Informaticae

2010

Vol. 104, nr 1/2

1-15

We study the stochastic events induced by MM-qfa's working on unary alphabets. We give two algorithms for unary MM-qfa's: the first computes the dimension of the ergodic and transient components of the non halting subspace, while the second tests whether the induced event is d-periodic. These algorithms run in polynomial time whenever the MM-qfa given in input has complex amplitudes with rational components. We also characterize the recognition power of unary MM-qfa's, by proving that any unary regular language can be accepted by a MM-qfa with constant cut point and isolation. Yet, the amount of states of the resulting MM-qfa is linear in the size of the corresponding minimal dfa. We also single out families of unary regular languages for which the size of the accepting MM-qfa's can be exponentially decreased.