Questions tagged [automata-theory]
Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
369
questions
-1
votes
0answers
21 views
How to start with proofs in CS?
My proving skills in CS is very poor. For eg- proving things by induction etc. Most proofs which I have seen were from automata theory and graphs.
Is there a textbook/ resource from where I can learn ...
2
votes
2answers
104 views
Translation of Counter-free automata into Linear Temporal Logic
There is a well-known equivalence between counter-free automata and Linear Temporal Logic (which is cited for example by [1]). However, I cannot find a concrete way to obtain an LTL formula from a ...
13
votes
0answers
248 views
Is this problem on unambiguous finite automata NP-complete?
An unambiguous finite automaton (UFA) is a nondeterministic finite automaton (NFA) such
that each word has at most one accepting path. In this post, for $n\in \mathbb{N}$, what I call an $n$-UFA (resp....
6
votes
1answer
157 views
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?
A function $f: A^* \to A^*$ is regularity-preserving if, for each regular language $L$ of $A^*$, the language $f^{-1}(L)$ is regular. I think I have a proof, as a consequence of more general results, ...
3
votes
1answer
92 views
Conditioning Probability on a Language With Measure 0
Let $\Sigma = \{ 1, 2, \ldots, n\}$ be some alphabet. Assume that you have a coin with n-sides (each side corresponds to a letter in $\Sigma$), and we get each letter with equal probability. Now you ...
2
votes
0answers
66 views
Necessary and sufficient condition for an infinite tree to be context-free
A Buchi automaton is non-empty iff it accepts an infinite word of the form $uv^\omega$ (here $u,v$ are finite words). In other words, if $\{w\}$ is an $\omega$-regular language, then it is of that ...
4
votes
1answer
300 views
Can we efficiently convert from NFA to smallest equivalent DFA?
Definitions
For any automaton $X$, let $L(X)$ denote the language recognized by $X$.
For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$.
...
2
votes
1answer
138 views
DFSA and NFSA intersection problem
Given $k$ deterministic FSAs of $n$ states the intersection of their languages is empty is decidable in $n^{o(k)}$ time is an open problem.
For unbounded $k$ it is known the problem is $PSPACE$ ...
6
votes
1answer
133 views
Random Cerny Conjecture
For simplicity, all DFAs will be using the binary alphabet $\{0,1\}$. Let $M$ be a synchronizable DFA. We let $p(M,n)$ be the probability that a random $x\in \{0,1\}^n$ will synchronize $M$.
We define ...
1
vote
1answer
66 views
Definition of Rabin acceptance condition for omega automatons [closed]
I've been trying hard to understand something. According to wikipedia and this paper, the definition of the Rabin acceptance condition involves a set of pairs of states. I've been told that the left ...
2
votes
1answer
88 views
NP-Completeness of Finding Minimum Automaton, in Gold's paper
I have been investigating "learning automatas", and I came across reference to Gold's papers several times: "Complexity Of Automaton Identification From Given Data", and "...
7
votes
2answers
443 views
Finite-State Automata over a real-valued alphabet
Consider a finite state set $Q$, with a distinguished start state $s\in Q$, as well as two functions: a transition function $\delta:Q\times\mathbb{R}\to Q$ and a final output function $F:Q\to\mathbb{R}...
4
votes
1answer
119 views
Decomposition of safety and liveness properties
In Alpern,Schneider 86 is described how to extract the automata that recognize safety and liveness properties from a Buchi automaton $m$. This shows that any property rapresented by a Buchi automaton ...
-1
votes
1answer
119 views
What is the time complexity of computing intersection and union of Nondeterministic Finite Automata (NFAs)?
Assume that $\mathcal{A} = (Q_A, \Sigma, \Delta_A, q_{i_A}, F_A)$ and $\mathcal{B} = (Q_B, \Sigma, \Delta_B, q_{i_B}, F_B)$ are two NFAs. What is the worst-case time complexity of computing $\mathcal{...
7
votes
0answers
99 views
Deciding whether DCFG is visibly pushdown
Is the following problem decidable?
If so, what's the best algorithm known?
Instance: a deterministic pushdown automaton $A$
Question: Does there exist (i) some partition of the alphabet into push, ...
12
votes
0answers
172 views
Regular languages accepted by an automaton with at most one transition per letter
I'm interested in the (very restricted) subset of regular languages for which there is an automaton having the following property: for every letter $a$ of the alphabet, the automaton has at most one ...
1
vote
0answers
34 views
Nominal Tree Languages i.e. with Binders and Infinite Symbols?
I'm wondering if there has been any research done into automata that accept languages of trees that can bind arbitrary variables, and are considered equal under alpha equivalence.
I've found so far:
...
3
votes
0answers
68 views
Deciding whether an arbitrary context-free grammar generates a deterministic push-down automata?
I know that it's undecidable whether an arbitrary context-free grammar is ambiguous, but is it decidable whether that grammar is deterministic? I can't find the answer to this question anywhere on the ...
7
votes
1answer
162 views
Isomorphism of ‘ordered’ DAGs / acyclic semiautomata
I am wondering what is known about the isomorphism problem on ordered DAGs, in particular how to find a canonical representative modulo isomorphism.
By ordered I mean that each vertex has a list of ...
9
votes
0answers
85 views
Reference request: DFA linear-time minimization
What is the most complicated kind of deterministic finite-state automaton that can be minimized in $O(n)$ time?
Here’s what I’ve been able to find so far:
The acyclic case has been solved. So any ...
11
votes
1answer
189 views
Planarity of planar finite automata intersection
It was shown that any regular language can be specified by planar $\varepsilon$-free nondeterministic finite automaton (Bezáková, Ivona, and Martin Pál. "Planar finite automata."). Is it ...
9
votes
2answers
329 views
Bounds on this Strategy for Separating Words
Question
Given binary string $z \in \{0,1\}^n$, let $f(z)$ be the smallest integer $k$ such that there exists a DFA with $k$ states, such that reading $z$ from a specific starting state, we end at a ...
1
vote
1answer
134 views
What kind of computational model is the brain? [duplicate]
I was wondering what kind of computational model is the human brain (as it seems superior to a Turing machine).
Another thing that should be a separate question, What would be a perfect computer model ...
3
votes
1answer
119 views
Rewrite relations - proof of correctness
Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular relation. We define the obligatory rewrite relation over $T$ as follows:
$$
R^{obl}(T) := N(T) \cdot (T \cdot N(T))^*
$$
$$
N(T) := Id(\Sigma^* ...
9
votes
2answers
543 views
Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?
Fix a deterministic finite automaton $A$ defining a regular language on the alphabet $\Sigma = \{0, 1\}$, and call the (Hamming) weight of a word $w \in \Sigma^*$ its number of $1$'s. Given a length $...
8
votes
0answers
131 views
Determining if transducer automaton has two states with intersecting images, without minimizing?
I work (in implementation!) with deterministic finite state automata with input and output; i.e. there are transitions (start state,input letter)$\to$(new state,output letter). Thus every state gives ...
3
votes
0answers
132 views
Weakest model of computation that can typecheck?
What's the weakest (known) model of computation (or smallest language class) that can decide whether a simply-typed lambda calculus program type checks? What about an (explicitly typed) CoC program?
6
votes
2answers
342 views
2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata
How can I convert a 2DFA to a normal DFA. Is there an algorithm/elegant way to do that ?
I've been researching this for a few days but I coundn't find anything. Actually I want to implement that in ...
5
votes
1answer
165 views
Is there any equation-based method for transforming Büchi-automata to omega-regular language?
I know there exists an equation-based method for transforming finite automata into regular language (or `regular expression'). The main idea is as follows.
First we construct a set of equations ...
7
votes
1answer
208 views
Languages whose Parikh image is recognizable
Let $\Sigma$ be some alphabet, and $p : \Sigma^* \to \mathbb N_0^{|\Sigma|}$ the Parikh map. A formal language $L \subseteq \Sigma^*$ is called a slip-language, if $p(L)$ is a semilinear set. By ...
3
votes
0answers
76 views
Incremental PDA emptiness testing?
Is there anything known about the problem of incremental emptiness testing for a pushdown automata?
Suppose you have a PDA with (up to) $n$ states and transitions, but instead of being given the ...
6
votes
1answer
108 views
What is the minimal class of subshifts for which conjugacy is known to be undecidable?
The question of whether two finite one directional shifts are conjugates is known to be decidable.
The same question for sofic shifts is famously open.
I have seen that some works manage to prove ...
2
votes
0answers
71 views
Proof: Why are MM-1QFA strictly more powerful than MO-1QFA? // Quantum automata
While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97). More ...
8
votes
7answers
838 views
NP-complete decision problems on deterministic automata
Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or ...
1
vote
1answer
61 views
Palindrome language and Finite Automata Machines [closed]
I'm a grad student in math. I'm unaware of available literature in theoretical computer science, so require suggestions for books. Here are the two topics I'm interested in exploring.
1) A complete ...
9
votes
1answer
178 views
Containment problem of an acyclic NFA in an NFA
Let $A$ and $B$ be NFAs, such that $A$ is acyclic.
In the general case, deciding whether $L(A)\subseteq L(B)$ is $PSPACE$-hard. However, since $A$ is acyclic, we know that for every $w \in L(A)$, it ...
10
votes
3answers
723 views
Maximum shortest word accepted by pushdown automata
Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ...
8
votes
4answers
555 views
Constraints on sliding windows
Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer.
I would like to know if anything is known on the time and space complexity with respect to $n$ to check for ...
4
votes
1answer
329 views
Are endmarkers necessary for Deterministic Pushdown Automata?
In the book by Kozen (Automata and Computability), the transition function of deterministic pushdown automata (DPDAs) is supposed, in contrast with non-deterministic pushdown automata (NPDAs), to ...
10
votes
1answer
455 views
What class of languages is recognized by finite-state automata with $k$ heads?
A DFA or NFA reads through an input string with a single head, moving left-to-right. It seems natural to wonder about finite-state machines that have multiple heads, each of which moves through the ...
4
votes
0answers
61 views
Translation from LTL with Past to LTL
Has it been charaterized the cost of the translation from LTL with Past to LTL?
In [Gab89] this translation is assumed to be non elementary and in "Temporal Logic with Past is Exponentially More ...
1
vote
1answer
126 views
Can we have more than one Deterministic Finite Automata diagrams for a set of strings? [closed]
Much like many math equations can be simplified. I am wondering if Deterministic Finite Automata diagrams can equal each other while some may be more simplified than others. I am following the youtube ...
5
votes
1answer
141 views
Are PDAs without ϵ moves and with bounded stack operation as powerful as PDAs with them?
It is known that PDAs without $\epsilon$ moves are as powerful as PDAs with them.
However, it seems to me that the proof allows several stack operations in one move. What happens if we allow at most ...
4
votes
1answer
100 views
Deterministic Realtime Languages
Book and Greibach (V. Book, Ronald & A. Greibach, Sheila. (1970). Quasi-realtime languages. Theory of Computing Systems. 4. 97-111. 10.1007/BF01705890.) prove that non-deterministic linear time ...
0
votes
0answers
70 views
Language recongized by a “quasi realtime register machine”?
Counter machines are very powerful. Even two counters suffice for making these Turing complete.
But, in simulating a Turing machine the counter machine encodes in its integers a large amount of data. ...
-2
votes
1answer
90 views
DPDA with parameterized states
I'm considering an extension of Sublime Text's syntax definition format. A syntax definition is, in essence, a specification of a deterministic pushdown automaton. I would like to extend the system to ...
-1
votes
1answer
110 views
What is the formal definition of a stacked based finite state machine?
The formal definition of a finite state machine is as follows:
A FSM is a quintuple:
($I$, $S$, $S$0, $T$, $F$)
$I$ - finite, non-empty input set
$S$ - finite, non-empty state set
$S$0 - initial state
...
3
votes
1answer
165 views
Intersection of two deterministic parity automata
Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
3
votes
1answer
81 views
Agnostic query learning for DFAs
Angluin's membership+equivalence query algorithm allows to efficiently and exactly learn a target $n$-state DFA. But what if the target DFA is huge, or the target concept is not even a regular ...
6
votes
1answer
188 views
Complexity of DFA intersection in this specific case?
In general, the size of the DFA that recognizes the intersection of $n$ languages is exponential in $n$. However, in my case I am computing the intersection of a very restricted subset of possible ...
