Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: equivalence problem

Sortuj według:

Ogranicz wyniki do:

Copyful Streaming String Transducers

Filiot Emmanuel, Reynier Pierre-Alain

Fundamenta Informaticae

2021

Vol. 178, nr 1/2

59--76

Copyless streaming string transducers (copyless SST) have been introduced by R. Alur and P. Černý in 2010 as a one-way deterministic automata model to define transductions of finite strings. Copyless SST extend deterministic finite state automata with a set of variables in which to store intermediate output strings, and those variables can be combined and updated all along the run, in a linear manner, i.e., no variable content can be copied on transitions. It is known that copyless SST capture exactly the class of MSO-definable string-to-string transductions, and are as expressive as deterministic two-way transducers. They enjoy good algorithmic properties. Most notably, they have decidable equivalence problem (in PSpace ). On the other hand, HDT0L systems have been introduced for a while, the most prominent result being the decidability of the equivalence problem. In this paper, we propose a semantics of HDT0L systems in terms of transductions, and use it to study the class of deterministic copyful SST. Our contributions are as follows:(i) HDT0L systems and total deterministic copyful SST have the same expressive power, (ii) the equivalence problem for deterministic copyful SST and the equivalence problem for HDT0L systems are inter-reducible, in quadratic time. As a consequence, equivalence of deterministic SST is decidable, (iii) the functionality of non-deterministic copyful SST is decidable, (iv) determining whether a non-deterministic copyful SST can be transformed into an equivalent non-deterministic copyless SST is decidable in polynomial time.

About the equivalence of the tangency relation of arcs

Konik T.

Prace Naukowe Instytutu Matematyki i Informatyki Politechniki Częstochowskiej

2008

Vol. 7, nr 2

43-49

In this paper the problem of the equivalence of the tangency relation Tl (a, b, k, p) of the rectifiable arcs in the generalized metric spaces is considered. Some sufficient conditions for the equivalence of this relation of the rectifiable arcs have been given here.

A New Class of Algebraic Series Having a Decidable Equivalence Problem

Honkala J.

Fundamenta Informaticae

2002

Vol. 53, nr 3,4

315-320

We introduce a new class of algebraic series with noncommuting variables having a decidable equivalence problem. As a tool we consider star roots of formal power series.

Solving equivalence of recurrent sequences in groups by polynomial manipulation

Ruohonen K.

Fundamenta Informaticae

1999

Vol. 38, Nr 1,2

135-148

Methods are described for reducing the equivalence problem for sequences defined by recurrence equations in various finitely generated groups to polynomial Gröbner basis constructions. The methods are simple enough to allow a straigthforward implementation in computer algebra programs.