Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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.

One Pebble Versus e log n Bits

Geffer V., Mereghetti C., Pighizzin G.

Fundamenta Informaticae

2010

Vol. 104, nr 1/2

55-69

We show that, for any ε> 0, there exists a language accepted in strong ĺźlog n space by a 2-way deterministic Turing machine working with a single binary worktape, that cannot be accepted in sublogarithmic weak space by any pebble machine (i.e., a 2-way nondeterministic Turing machine with one pebble that can be moved onto the input cells). Moreover, we provide optimal unary lower bounds on the product of space and input head reversals for strong and weak pebble machines accepting nonregular languages.