12

No, the exponential lower bound for determinization holds already for unambiguous NFAs. This is obtained as follows: Consider the alphabet $\{a,b\}$, and the language: $$L_k=\{w\in \{a,b\}^*:\text{the $k$-th before last letter in }w\text{ is }b\}$$ It's easy to construct an unambiguous NFA for $L_k$: the NFA guesses when the $k$ before last letter is, and ...


10

Automata over infinite alphabets have been studied in many contexts (see e.g., this paper as a starting point). Usually, the model is somewhat different than what you suggest, since just having an infinite alphabet is not very interesting, for the following reason: Given an automaton with $n$ states, there are only $2^{n^2}$ transition matrices. Thus, if ...


6

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 reading a word $u$, $\mathcal A'$ will remember the state reached in $\mathcal A$ by $f(u)$, together with the action of $u$ on all states of $\mathcal A$. More ...


5

I think this problem has little to do with Cerny's conjecture. There the problem is to find a word that works for every pair of states. Here it is enough to show that the word will work whp. for any pair of states. An exponential lower bound on $f$ can be given as follows. Take a DFA whose states are $v_1,\ldots,v_k$ and the transition function is such that ...


5

The second section of Robson's "Separating strings with small automata" proves $F(n) = O((n \log n)^{1/2})$. The string sequence $(10^n)^n$ gives a lower bound of $\Omega(n^{1/2})$. If the automaton has $<n$ states then both of the sequences $\delta_0^{\circ m} (\delta_{(10^n)^{n-1}1}(q_0))$ and $\delta_{10^n}^{\circ m}(q_0)$ will reach a cycle ...


5

As mentioned in the comments, the translation is shown in: Volker Diekert and Paul Gastin. "First-order definable languages." (2008) http://www.lsv.fr/Publis/PAPERS/PDF/DG-WT08.pdf And it goes via a characterization of $LTL$ as $FO[<]$.


4

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 definition for "ambiguity" in regular expressions (how many valid parses are there for a given word), and show how to construct an NFA that will have the same ...


4

What if you don't assume a finite state space, but rather allow the set Q to be R, yet require delta to be "nice", e.g., smooth and easily computable? Then this presumably defines a restricted class of functions over sequences of reals. Has this question been studied?


4

See here: https://cs.stackexchange.com/questions/61113/does-a-given-e-nfa-accepts-all-the-strings "checking whether an NFA accepts all strings is PSPACE-complete". In particular, if an NFA accepts all strings then its smallest equivalent DFA has size 1, and so a positive answer to your question would imply P=PSPACE.


4

Regarding question (1): As long as $k$ is $\Omega(n^c)$ for some $c > 0$, then the problem is $PSPACE$-complete. See this paper by Klaus-Jörn Lange and Peter Rossmanith (1992) for some related results. https://doi.org/10.1007/3-540-55808-X_33 Regarding question (2): Say that the intersection problem is parameterized by the number of FSA's. If this ...


4

The sizes $|Q_n|$ can grow exponentially even in the context of question 1 (and thus questions 2 and 3 as well). For $n = 2 k$ even, define the grammar $G_n$ of size $O(n)$ by $$ \begin{align*} S \to {} & S_0 \\ S_i \to {} & 0 S_{i+1} 0 \mathbin{|} 1 S_{i+1} 1 \\ S_k \to {} & \epsilon \end{align*} $$ where $i$ runs from $0$ to $k-1$. There is an ...


4

Sorry to provide the same answer as for this question, but this was proved in [1, Theorem 3.1]. [1] J. Cohen, D. Perrin and J.-É. Pin, On the expressive power of temporal logic for finite words, J. Comput. System Sci. 46 (1993), 271-294.


3

I don't know of a general approach to handle this, but in the case of $\omega$-regular languages, this has been done. One approach, which I think is first introduced in the paper Computing Conditional Probabilities in Markovian Models Efficiently is the following: Given the language $L$, let $D$ be a DPW for it. Now, start by constructing a Markov chain $M$ ...


3

The following (discussed in another thread, and as of this edit I don't know the answer yet) is Problem 7.36 from Sipser Third edition: Show that the following problem is NP-complete. You are given a set of states $Q = \{ q_0, q_1, \ldots, q_l\}$ and a collection of pairs $\{ (s_1, r_1), \ldots, (s_k, r_k)\}$ where the $s_i$ are distinct bitstrings and $r_i$...


3

Yes. The automata in question are often called "Looping" automata (so you have a keyword to start from). A possible starting point is the following paper: https://faculty.idc.ac.il/udiboker/files/MullerAutomata.pdf A looping automaton can be described as $\left<Q,\Sigma,\delta,Q_0\right>$ where the components are states, alphabet, transition ...


3

I seems that I was quite confused back then. This language class is precisely the language class of those languages, whose commutative closure is regular. Let $\Sigma = \{a_1, \ldots, a_k\}$. One implication is given in the question. For the other, suppose the commutative closure of $L \subseteq \Sigma^*$ is regular, i.e., the set $p^{-1}(p(L))$ is regular. ...


2

As Marzio De Biasi states, since $k$ is fixed, this is equivalent to a NFA. To deal with the "universal" requirement, use the subset construction to convert to a DFA. In particular: the state of the DFA is the set of configurations of the counter machine that can be reached after reading the input so far. Since $k$ is fixed, there are only ...


2

After discussing it further with a3nm, I propose an algorithm that is different than Neal's algorithm and works in a more general setting. The approach gives polynomial delay algorithm but it uses exponential space. The only two properties that we will be using are : (1) The problem is self-reducible, in the sense that if I am given an automaton $A$ and $u \...


2

A result relating to DFAs(or Failure DFAs) and compressibility that shows NP-completeness via failure transitions - this work relates to whether there are efficient algorithms for DFA compressibility Another result based on Gold's (reference in the other answer) Grammatical Inference framework that shows Minimal Separating Automata is NP-complete, Related ...


1

After more and more digging, here is what I found: First reference: Introduction to Automata Theory, Languages, and Computation 3rd Edition. Specifically, theorem 4.26 indicates that the provided algorithm constructs a minimum state machine M for a A such that M has as few states as any DFA equivalent to A. This was my original understanding, so the answer ...


1

You mean the worst-case complexity of computing NFAs accepting $L(\mathcal{A}) \cup L(\mathcal{B})$ and $L(\mathcal{A}) \cap L(\mathcal{B})$? For union it's easy to achieve $O\left(|Q_A| + |Q_B|\right)$ as we need to add new initial state $q_{\ast}$ and add transitions of kind $(q_{\ast}, a, q)$ whether $(q_{i_A}, a, q) \in \Delta_A$ or $(q_{i_B}, a, q) \in \...


Only top voted, non community-wiki answers of a minimum length are eligible