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: unambiguity

Sortuj według:

Ogranicz wyniki do:

Unambiguous Functions in Logarithmic Space

Herman G., Soltys M.

Fundamenta Informaticae

2012

Vol. 114, nr 2

129-147

We investigate different variants of unambiguity in the context of computingmulti-valued functions. We propose a modification to the standard computation models of Turing machines and configuration graphs, which allows for unambiguity-preserving composition. We define a notion of reductions (based on function composition), which allows nondeterminism but controls its level of ambiguity. In light of this framework we establish reductions between different variants of path counting problems. We obtain improvements of results related to inductive counting.

Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages

Anselmo M., Giammarresi D., Madonia M.

Fundamenta Informaticae

2010

Vol. 98, nr 2/3

143-166

Recognizable two-dimensional languages (REC) are defined by tiling systems that generalize to two dimensions non-deterministic finite automata for strings. We introduce the notion of deterministic tiling system and the corresponding family of languages (DREC) and study its structural and closure properties. Furthermore we show that, in contrast with the one-dimensional case, there exist other classes between deterministic and non-deterministic families that we separate by means of examples and decidability properties.

Interpreted Trajectories

Domaratzki M., Rozenberg G., Salomaa K.

Fundamenta Informaticae

2006

Vol. 73, nr 1-2

81-97

We introduce generalized trajectories where the individual symbols are interpreted as operations performed on the operand words. The various previously considered trajectory-based operations can all be expressed in this formalism. It is shown that the generalized operations can simulate Turing machine computations. We consider the equivalence problem and a notion of unambiguity that is sufficient to make equivalence decidable for regular sets of trajectories under nonincreasing interpretations.