The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying 541 – 560 of 948

Showing per page

On the expressive power of the shuffle operator matched with intersection by regular sets

Joanna Jȩdrzejowicz, Andrzej Szepietowski (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We investigate the complexity of languages described by some expressions containing shuffle operator and intersection. We show that deciding whether the shuffle of two words has a nonempty intersection with a regular set (or fulfills some regular pattern) is NL-complete. Furthermore we show that the class of languages of the form L R , with a shuffle language L and a regular language R , contains non-semilinear languages and does not form a family of mildly context- sensitive languages.

On the expressive power of the shuffle operator matched with intersection by regular sets

Joanna Jędrzejowicz, Andrzej Szepietowski (2010)

RAIRO - Theoretical Informatics and Applications

We investigate the complexity of languages described by some expressions containing shuffle operator and intersection. We show that deciding whether the shuffle of two words has a nonempty intersection with a regular set (or fulfills some regular pattern) is NL-complete. Furthermore we show that the class of languages of the form L R , with a shuffle language L and a regular language R, contains non-semilinear languages and does not form a family of mildly context- sensitive languages.

On the Influence of the State Encoding on OBDD-Representations of Finite State Machines

Christoph Meinel, Thorsten Theobald (2010)

RAIRO - Theoretical Informatics and Applications

Ordered binary decision diagrams are an important data structure for the representation of Boolean functions. Typically, the underlying variable ordering is used as an optimization parameter. When finite state machines are represented by OBDDs the state encoding can be used as an additional optimization parameter. In this paper, we analyze the influence of the state encoding on the OBDD-representations of counter-type finite state machines. In particular, we prove lower bounds, derive exact...

On the invertibility of finite linear transducers

Ivone Amorim, António Machiavelo, Rogério Reis (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Linear finite transducers underlie a series of schemes for Public Key Cryptography (PKC) proposed in the 90s of the last century. The uninspiring and arid language then used, condemned these works to oblivion. Although some of these schemes were afterwards shown to be insecure, the promise of a new system of PKC relying on different complexity assumptions is still quite exciting. The algorithms there used depend heavily on the results of invertibility of linear transducers. In this paper we introduce...

Currently displaying 541 – 560 of 948