Questions tagged [automata-theory]
Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
356
questions
-1
votes
1answer
70 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{...
8
votes
0answers
95 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
162 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
30 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
57 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
137 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
84 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
181 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
283 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
124 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
116 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
359 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
129 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
129 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
244 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
160 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
0answers
118 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
50 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
97 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
69 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
544 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
52 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
168 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
541 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
516 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
266 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
276 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
54 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
88 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
133 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
98 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
84 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
103 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
146 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
78 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
179 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
214 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
104 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, ...
2
votes
0answers
56 views
Regular Tree Languages are closed under quotient?
The Wikipedia page for Regular Tree Grammars notes that if $L_1$ and $L_2$ are regular tree languages, than $L_1 \setminus L_2$ is as well. However, it doesn't define this quotient operation for trees,...
9
votes
1answer
294 views
Turing Machines as Coalgebras
I'm looking to write a survey on the method of representing the dynamics of state-based computation within the framework of coalgebras. So far I've managed to find papers on coalgebra representations ...
8
votes
1answer
169 views
A conjecture related to the Cerny conjecture - counterexample/reference request
The Cerny conjecture is the statement that any synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. The best current upper bound for the length of a ...
3
votes
2answers
178 views
Compactness of domino tilings
I've read in Lemma 2 of the paper 1 that if every square region of the plane admits a tiling, then the whole plain admits a tiling, but the proof is omitted. This sounds like a compactness property, ...
5
votes
1answer
241 views
Name for a special family of languages?
I was wondering whether there is a standard name in the literature for the following family $\mathcal{F}$ of languages over any finite alphabet $\Sigma = \{a_1,\ldots,a_k\}$:
$\mathcal{F}$ consists ...
2
votes
1answer
307 views
Automata as term rewriting systems
It came to my mind that automata (say to start DFA) can be thought as a special kind of rewriting systems. So if one has a word w , one tries to reduce it to the $\epsilon$ word. In other words ...
9
votes
3answers
437 views
Continuous mathematics and formal language theory
Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics.
For example, solving the intersection non-emptiness problem for a context-free ...
11
votes
2answers
443 views
Does a given regular language contain an infinite prefix-free subset?
A set of words over a finite alphabet is prefix-free if there are no two distinct words where one is a prefix of the other.
The question is:
What is the complexity of checking whether a regular ...
4
votes
1answer
119 views
Applications of Christol theorem
I'm looking forward to know about applications of Christol theorem mentioned in Jefrrey Shallit's Number theory and formal languages. One of them is purely algebraic: if $f, g \in \mathbb{F}_q[[z]]$ ...
10
votes
0answers
117 views
Are there cascade decompositions of machines that are more general than finite automata?
The idea of decomposing automata and their associated semi-groups into irreducible sub-components is due to Krohn & Rhodes and has been explored relatively thoroughly. Krohn & Rhodes gave an ...
7
votes
2answers
521 views
Are all turing machines paths predictable?
I was recently studying partial solutions to the halting problem and came across the problem which I discuss below. In particular I was studying when it was computable to tell if a turing machine has ...
