Tag Info

Automata learning without counterexamples

Consider password automata: for each $w\in\{0,1\}^n$, the DFA $M_w$ accepts the language $\{w\}$. In this case, a membership query is the same as an equivalence query --- and clearly, you'll need ...
• 10.6k
Accepted

Parameterized complexity of inclusion of regular languages

The particular case of language universality (are all words accepted ?) is PSPACE-complete for regular expressions or NFAs. It answers your question: in general the problem stays PSPACE-complete even ...
• 8,923

• 23.1k

Obscure characterizations of the regular languages

I know it is frowned upon to promote one's own results, but it turns out that I wrote an article precisely on this topic. So let me add a few characterizations of regular languages not already ...
• 5,101

• 9,707

Transition monoid membership for DFAs

Decidability It's decidable. There are only finitely many possible functions $f:Q \to Q$, so you can model this as a graph reachability problem, with one vertex per function and an edge $g \to h$ if ...
• 12.3k

In the context of regular languages, must the alphabet be finite?

It makes sense in some contexts in mathematics to consider strings or languages over infinite alphabets. For instance, this concept is used in the strong version of Higman's lemma. But a finite ...
• 51.1k

Counting words accepted by a regular grammar

I think this is a hard counting problem, see this paper: Counting the size of regular sequences of given length is #P-complete: S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting and random generation ...
Accepted

Finding a minimal DFA whose language has a desired intersection with another

$M_C$ must accept every word of $S^+ = B$ and reject every word of $S^- = A \setminus B$. Let $A$ and $B$ be finite and such that both $S^+$ and $S^-$ are non-empty. Then exact computation of $M_C$ ...

Planarity of planar finite automata intersection

As mentioned in my comment, the usual product construction does not preserve planarity. In fact, there is an intersection of regular languages that can be described by a nonplanar NFA with $n$ states, ...
• 6,665
Accepted

(N)DFA with same initial/accepting state(s)

This question is solved for deterministic automata and for unambiguous automata in the book [1] [1] J. Berstel, D. Perrin, C, Reutenauer, Codes and automata, Vol. 129 of Encyclopedia of Mathematics ...
• 5,101

In the context of regular languages, must the alphabet be finite?

The usual convention in formal languages and automata theory is that an alphabet is finite. However, there are certainly some cases where it's useful to think of an alphabet being infinite. For ...
• 6,985

Hierarchies in regular languages

I recently came across this paper which may give another relevant example (cf. the last sentence of the abstract): Guillaume Bonfante, Florian Deloup: The genus of regular languages. From the ...
• 5,598
Accepted

The complexity of conversion from a regular expression to a nondeterminsitic automata and back after changing initial and final states

As observed in the proof of Theorem 6 (later dubbed the "Star Height Lemma") of Gruber/Holzer ICALP 2008, when converting a regular expression into an $\varepsilon$-NFA, then the underlying ...
• 6,665
Accepted

Testing whether letters can be scheduled to achieve a word in a regular language

The problem is NP-hard for $L = A^*$ where $A$ is the finite language containing the following words: $x111$, $x000$, $y100$, $y010$, $y001$, $00c11$, $01c10$, $10c01$, and $11c00$ The reduction is ...
• 2,883

Complexity of checking if two words have an interleaving in a language

For a word $w=w_1\ldots w_{\ell}$ and for two integers $i,j$ with $1\le i\le j\le \ell$ we denote by $w(i,j)$ the subword $w_iw_{i+1}\ldots w_j$ of $w$. Furthermore we let $w(0,0)$ denote the empty ...
• 5,792
Accepted

Complexity of DFA intersection in this specific case?

The precise bound is $2^n$. The lower bound was given in the comments: the state complexity of $A^*a_1A^* \cap \dotsm \cap A^*a_nA^*$ is $2^n$. For the upper bound, it suffices to observe that if $B$ ...
• 5,101
Accepted

Kleene Algebra for star-free regular expressions

You might be interested in bounded synchronization delay expressions. See [1] for details on these expressions. To sum up, they are equivalent to star-free expressions, but instead of using complement,...
• 8,923
Accepted

Is the function $f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$ regularity-preserving?

Here is a proposition for an elementary proof: Let $\mathcal A=(A,Q,q_0,F,\delta)$ be a DFA for $L$, we want to build a DFA $\mathcal A'=(A,Q',q_0',F',\delta')$ for $f^{-1}(L)$. Intuitively, when ...
• 8,923
Accepted

Regular Expressions that converts into unambiguous automata

The paper Ambiguity in Graphs and Expressions (Book et al., 1971) discusses constructing regular expressions that preserve the ambiguity of the input NFA and vice versa. That is, they give a ...
• 399
Accepted

star height of star-free languages

The examples of arbitrary star-height given on the wikipedia page on the star-height problem are star-free: On arbitrary alphabet: :\begin{alignat}{2} e_1 &= a_1^* \\ e_2 &= \left(a_1^*a_2^*...
• 8,923

minimizing size of regular expression

It is PSPACE-complete to decide whether an expression accepts all words, i.e. is equivalent to $(a|b|c|...)^*$. It is not hard to get convinced that in this proof of PSPACE-completeness (see e.g. ...
• 8,923
Accepted

Pumping Lemma over 2 way Automaton

Claim: If $M$ is a 2-way NFA (without endmarkers) with $n$ states which acceptes a unary language $L\not=\emptyset$ then there is a word $w \in L$ of length at most $3n+5$. Proof sketch: Let $v\in L$ ...
• 1,417
Accepted

NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?

The paper [HP06] is in the spirit of your idea, although in a different direction, in the context of infinite words. It can be adapted more easily to finite words. In the powerset construction, we ...
• 8,923
Accepted

Existence of injective length-preserving rational function to a smaller alphabet

It turns out the answer is "no": in [2] the authors show that a regular language $L$ exists with density $\rho_L(n) \leq |B|^n$ such that no regular language over $B$ has the same density; ...
• 1,234
Accepted

Is there a simple characterization of regular languages closed under circular shifts?

We can propose an automaton model characterizing regular circular languages: a C-automaton is an NFA where all states are initial. A run must see an accepting state somewhere, and must start and end ...
• 8,923
Accepted

Automata : Language Containment, Minimality & Graph Homomorphism

For inclusion, using your condition that non-final states can be mapped to final states does not work. Consider for instance that $A$ is a rejecting sink $p_0$, and $B$ is the minimal automaton for ...
• 8,923