People who code: we want your input. Take the Survey

# Tag Info

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 ...

8

If you only need to order the outgoing edges the problem is GI complete. Reduce from GI of directed graphs. Given a digraph $D$ make a new one $D’$ as follows: Make a vertex in $D’$ for every vertex of $D$ and every arc of $D$. For every arc $u \rightarrow v$ of $D$, add the arcs: $uv \rightarrow u$ and $uv \rightarrow v$ in $D’$ (in this order). Clearly $D’$...

6

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, whereas any equivalent planar NFA needs $\Omega(\frac{n^2}{\log\log n})$ states. The proof is indirect and goes via a lower bound on regular expression size: ...

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

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[<]$.

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

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 ...

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

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.

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?

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

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

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$...

2

This is pretty much an open problem and subject to active research. There are a few proposals available. Here are some of the latest ones: Brain computation by assemblies of neurons Christos H. Papadimitriou, Santosh S. Vempala, Daniel Mitropolsky, Michael Collins, Wolfgang Maass Proceedings of the National Academy of Sciences Jun 2020, 117 (25) 14464-14472;...

2

To simplify, let $D$ be the domain of $T$ and let $R = \{\epsilon\} \cup (\Sigma^* \setminus \Sigma^*D\Sigma^*)$. Then by definition $$N(T) = Id_R \quad \text{and} \quad R^{obl}(T) = N(T)(TN(T))^*.$$ Here is a formal way to justify your idea. Let $(u,v) \in \Sigma^* \times \Sigma^*$. By definition, $(u,v) \in R^{obl}(T)$ if and only if $(u,v)$ can be ...

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 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 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 ... 2 The conjecture does not hold: Let$L$be the set of prefixes of$(c^*ac^*b)^*$. Then$L'=(c^*ac^*b)^\omega+ (c^*ac^*b)^*c^\omega+(c^*ac^*b)^*c^*ac^\omega$. Take the word$\eta=(c^1ac^1b)(c^2ac^2b)(c^3ac^3b)\dots \in L'$. For all$k\in\mathbb N$, we can show that$PF_k(\eta)\not\subseteq L'$, as witnessed by$$u_k=(c^1ac^1b)(c^2ac^2b)\dots (c^kac^kb)c^kb c^\... 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