Currently displaying 1 – 6 of 6

Showing per page

Order by Relevance | Title | Year of publication

Closure properties of hyper-minimized automata

Andrzej Szepietowski — 2011

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

Two deterministic finite automata are almost equivalent if they disagree in acceptance only for finitely many inputs. An automaton is hyper-minimized if no automaton with fewer states is almost equivalent to . A regular language is canonical if the minimal automaton accepting is hyper-minimized. The asymptotic state complexity () of a regular language is the number of states of a hyper-minimized automaton for a language finitely different from . In this paper we show that: (1)...

Lower Space Bounds for Accepting Shuffle Languages

Andrzej Szepietowski — 2010

RAIRO - Theoretical Informatics and Applications

In [6] it was shown that shuffle languages are contained in (log ) and in . In this paper we show that nondeterministic one-way logarithmic space is in some sense the lower bound for accepting shuffle languages. Namely, we show that there exists a shuffle language which is not accepted by any deterministic one-way Turing machine with space bounded by a sublinear function, and that there exists a shuffle language which is not accepted with less than logarithmic space even if we allow two-way nondeterministic...

Closure properties of hyper-minimized automata

Andrzej Szepietowski — 2012

RAIRO - Theoretical Informatics and Applications

Two deterministic finite automata are almost equivalent if they disagree in acceptance only for finitely many inputs. An automaton is hyper-minimized if no automaton with fewer states is almost equivalent to . A regular language is canonical if the minimal automaton accepting is hyper-minimized. The asymptotic state complexity () of a regular language is the number of states of a hyper-minimized automaton for a...

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

Joanna JȩdrzejowiczAndrzej 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ędrzejowiczAndrzej 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 and a regular language , contains non-semilinear languages and does not form a family of mildly context- sensitive languages.

Page 1

Download Results (CSV)