Zobrazeno 1 - 10
of 190
pro vyhledávání: '"Brzozowski, Janusz A."'
In a simple pattern matching problem one has a pattern $w$ and a text $t$, which are words over a finite alphabet $\Sigma$. One may ask whether $w$ occurs in $t$, and if so, where? More generally, we may have a set $P$ of patterns and a set $T$ of te
Externí odkaz:
http://arxiv.org/abs/1806.04645
Autor:
Brzozowski, Janusz A., Davies, Sylvie
A regular language $L$ is union-free if it can be represented by a regular expression without the union operation. A union-free language is deterministic if it can be accepted by a deterministic one-cycle-free-path finite automaton; this is an automa
Externí odkaz:
http://arxiv.org/abs/1711.09149
The \emph{state complexity} of a regular language $L_m$ is the number $m$ of states in a minimal deterministic finite automaton (DFA) accepting $L_m$. The state complexity of a regularity-preserving binary operation on regular languages is defined as
Externí odkaz:
http://arxiv.org/abs/1710.06000
Autor:
Brzozowski, Janusz A.
We survey recent results concerning the complexity of regular languages represented by their minimal deterministic finite automata. In addition to the quotient complexity of the language -- which is the number of its (left) quotients, and is the same
Externí odkaz:
http://arxiv.org/abs/1702.05024
Autor:
Brzozowski, Janusz A., Davies, Sylvie
A regular language $L$ is non-returning if in the minimal deterministic finite automaton accepting it there are no transitions into the initial state. Eom, Han and Jir\'askov\'a derived upper bounds on the state complexity of boolean operations and K
Externí odkaz:
http://arxiv.org/abs/1701.03944
Autor:
Brzozowski, Janusz, Sinnamom, Corwin
A language $L$ over an alphabet $\Sigma$ is suffix-convex if, for any words $x,y,z\in\Sigma^*$, whenever $z$ and $xyz$ are in $L$, then so is $yz$. Suffix-convex languages include three special cases: left-ideal, suffix-closed, and suffix-free langua
Externí odkaz:
http://arxiv.org/abs/1610.00728
Autor:
Brzozowski, Janusz, Sinnamon, Corwin
We study the state complexity of binary operations on regular languages over different alphabets. It is known that if $L'_m$ and $L_n$ are languages of state complexities $m$ and $n$, respectively, and restricted to the same alphabet, the state compl
Externí odkaz:
http://arxiv.org/abs/1609.04439
Autor:
Brzozowski, Janusz, Sinnamon, Corwin
A language $L$ over an alphabet $\Sigma$ is prefix-convex if, for any words $x,y,z\in\Sigma^*$, whenever $x$ and $xyz$ are in $L$, then so is $xy$. Prefix-convex languages include right-ideal, prefix-closed, and prefix-free languages. We study comple
Externí odkaz:
http://arxiv.org/abs/1605.06697
Autor:
Brzozowski, Janusz
I study the state complexity of binary operations on regular languages over different alphabets. It is well known that if $L'_m$ and $L_n$ are languages restricted to be over the same alphabet, with $m$ and $n$ quotients, respectively, the state comp
Externí odkaz:
http://arxiv.org/abs/1602.01387
Publikováno v:
In Descriptional Complexity of Formal Systems (DCFS 2016), volume 9777 of LNCS, pages 73--86, 2016
We investigate the shuffle operation on regular languages represented by complete deterministic finite automata. We prove that $f(m,n)=2^{mn-1} + 2^{(m-1)(n-1)}(2^{m-1}-1)(2^{n-1}-1)$ is an upper bound on the state complexity of the shuffle of two re
Externí odkaz:
http://arxiv.org/abs/1512.01187