Questions tagged [automata-theory]
Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
367
questions
6
votes
1answer
122 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
89 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
60 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
247 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)$.
...
-1
votes
0answers
48 views
Complexity of recognizing strings in $NPDA$
If an $NPDA$ has $k=poly(n)$ states with branching factor $m$ and the input strings are limited so that stack sizes are $d=poly(n)$ in length what is the best algorithm to parse strings on length $n$ ...
2
votes
1answer
123 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
118 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
64 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
81 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
440 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
111 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
96 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
97 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
169 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
33 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
61 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
150 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
188 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
302 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
127 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
118 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^* ...
8
votes
1answer
388 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
130 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
131 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
299 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
163 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 ...
5
votes
1answer
159 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
63 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
104 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
70 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 ...
7
votes
5answers
601 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
58 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
172 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
619 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
538 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
295 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
384 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
59 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
106 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
136 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
99 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
87 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
105 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
158 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
79 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
182 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 ...
0
votes
1answer
219 views
Where does a C-like language without heaps belong in the automata hierarchy?
Assume that the language C', unlike C, has well-defined semantics, but has similar features: pointers and manual memory management through malloc and free. Assume that C'' is the same as C' without ...
2
votes
0answers
107 views
Notion of “quotient” or “inverse” for recognizable tree languages?
Related to my previous question but this time I have a better idea of what I'm actually asking.
I'm looking at the following operation on recognizable tree languages (i.e. regular tree grammars, ...
