Questions tagged [automata-theory]
Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
416
questions
6
votes
2
answers
420
views
Error in Robson's proof about separating strings?
One of my students discovered a possible mistake in Robson's classic paper Separating strings with small automata.
The issue is in the proof of Theorem 1, giving the simpler bound $O(\sqrt{n\log n})$.
...
- 13.9k
6
votes
0
answers
64
views
Updating (minimal) DFA incrementally
Is there algorithm to incrementally update (minimal) DFA? Namely, having relatively large minimized DFA I want to update it incrementally using union and sudtraction with other (relatively small, ...
- 421
2
votes
1
answer
277
views
Deciding finiteness of regular language is NL-complete?
I've been reading the following Habilitation thesis where the author claims (pg. 29):
... First, deciding whether the language of an NFA is finite is in NL ...
I'm having trouble seeing why this ...
user70406
0
votes
2
answers
58
views
Representing/Modelling fields and methods in the context of programming as automata
I am trying to represent/model fields and methods in the context of programming as automata. For instance, let's say that I have field1 with state equal to 2, ...
- 129
0
votes
0
answers
62
views
How to reduce a code down to its configuration
I have built a system where from atomic information of a UI code I could generate a framework specific code. Here is the concept https://github.com/imvetri/ui-editor. For example, the user of this ...
- 99
1
vote
0
answers
91
views
Equivalence between GNFA and NFA/DFA
In Section 1.3 of the 3rd edition of Michael Sipser’s Introduction to the Theory of Computation, it is proven that regular expressions are equivalent to deterministic finite automatas (DFAs). That is, ...
- 111
7
votes
1
answer
151
views
Complexity of the inevitability problem over monoids
I am interested in the complexity of following problem:
Inevitability problem in monoids
Input: two regular languages $K$, $L$ specified by finite monoids $M_K$ and $M_L$ (+ morphisms and accepting ...
- 143
7
votes
1
answer
333
views
Converting 2-ambiguous NFA to unambiguous NFA
This must be known, but somehow I can't locate a reference about this. Let $A$ be a nondeterministic finite automaton (NFA) over words of an alphabet $\Sigma$. I say that $A$ is unambigous if, for ...
- 8,896
1
vote
0
answers
107
views
Real life application of two-way DFA
I am currently studying two-way DFA and I couldn't find and research anything on its real-life applications if there are any. I am very unsure where it could be used and any ideas would be great. tyia
- 11
0
votes
0
answers
65
views
Construction of a PDA for the binary and decimal representation of a number
I have the solution with me for this question but I have really hard time understanding the construction. Can anyone may be break it down in a simpler way?
Problem:
Given $n \in \mathbb{N}^+$. ...
- 11
2
votes
1
answer
142
views
Is $a^m b^n$ where $m - n \sqrt{2} \ge 0$ context-free?
Is the language $a^m b^n$ where $m - n \sqrt{2} \ge 0$ a context-free language? I’m suspecting that it’s not, but I haven’t been able to prove so using the pumping lemma for context-free languages.
...
- 123
4
votes
0
answers
84
views
Linear-time maze exploration for finite automaton with pebbles?
Blum and Kozen have shown that a robot with the computational capabilities of a finite automaton can visit all $n$ cells in a quadratic maze when the robot is equipped with two pebbles which it may ...
- 41
6
votes
0
answers
118
views
What is the Simplest type of automaton that can simulate all DFAs?
During recent research in a somewhat unrelated field (Spin Physics), I stumbled across a subclass of regular languages. The context of the research poses the question what the minimal power of the ...
- 161
5
votes
1
answer
111
views
Logical Equivalents of Finite State Transducers
There's a notion of "regular" function on words in automata theory that corresponds nicely to functions in WS1S/Büchi Arithmetic/the logic of words with a prefix and equal-length relation. ...
- 279
3
votes
0
answers
107
views
State-based vs. transition-based definitions of alternating automata
Maybe this is a naïve question but I'm having difficulties finding the answer in the literature.
Alternating finite automata (AFA) are usually defined in modern literature in the following terms. An ...
- 1,588
0
votes
0
answers
64
views
Number of quantifier alternations in prenex form of a formula
I'm currently studying hyperlogics and in particular HyperLTL/CTL*.
In model checking algorithms for such logics the number of quantifier alternations appearing in a formula can play an important role ...
0
votes
0
answers
135
views
The difference between the 1st and 2nd editions. "Compilers Principles, Techniques, and Tools" by Aho, Sethi and Ullman
I bought "Compilers Principles, Techniques, and Tools 1st Edition" by Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman long years ago and it has been sitting on my bookshelf ever since.
I ...
- 101
4
votes
1
answer
183
views
Pumping lemma for CFL intersection
The class of context-free languages is not closed under intersection. For example, the language $L=\{a^nb^nc^n : n\geq 0\}$ is not context-free, but it is an intersection of two context-free languages....
- 303
11
votes
12
answers
5k
views
Theoretical Computer Science vs other Sciences?
So I‘m in my fifth semester studying Computer Science at a German university, so I‘ve only scratched the surface of Theoretical Computer Science, namely Logic, Formal Languages, Automata Theory, ...
- 127
4
votes
0
answers
71
views
Equivalent Characterizations of Semilinear Sets
Coming from an automata theory background, the semilinear sets seem like an ideal candidate for having lots of equivalent characterizations.
I am already familiar with a few well known ones:
Sets ...
- 279
6
votes
1
answer
276
views
Relationship between the transition monoid of an automaton and its adjacency matrix
Let $A=(Q,\Sigma, \Delta, q_0, F)$ be an NFA over an alphabet $\Sigma$, $M(A)$ be its transition monoid.
For all $a\in\Sigma$, let $S_a\in\mathbb{B}^{|Q|\times|Q|}$ be the adjacency matrix of $A$ ...
- 1,588
5
votes
0
answers
150
views
Arithmetization of finite automata
Is there any standard way to encode the language accepted by a finite automaton by an arithmetic formula?
A particular way of doing this would be to extend the language of existential integer linear ...
- 921
2
votes
1
answer
421
views
Are regular expressions inherently more difficult to construct than DFAs for humans?
When I am asked to construct a regular expression and DFA that would accept a language $L$, I usually find it much easier to construct the DFA (almost coming mechanically for me) than it is to ...
- 1,078
3
votes
2
answers
118
views
Encoding of finite automata in Intersection Non-Emptiness problem
The intersection non-emptiness problem is defined as follows:
Given a list of deterministic finite automata as input, the goal is to determine whether or not their associated regular languages have a ...
- 921
1
vote
0
answers
90
views
Alternative notions of bisimulation
Suppose $(S, \Lambda, \rightarrow)$ is a labeled transition system. A bisimulation is a relation $R \subseteq S \times S$ s.t. $\forall \alpha \in \Lambda$ and $\forall p, q \in S$ with $R(p,q)$,
$\...
- 11
3
votes
3
answers
449
views
Intersection non-emptiness problem over regular expressions and NFA
The intersection non-emptiness problem is defined as follows:
Given a list of deterministic finite automata as input, the goal is to determine whether or not their associated regular languages have a ...
- 921
3
votes
1
answer
195
views
Algorithms for equivalence of 2 way finite automata (2DFA)
I'm interested in the computational complexity of deciding equivalence of 2DFAs.
It is known that converting 2DFA to DFA can incur a blow up in states. However I'm not sure whether this automatically ...
- 135
1
vote
0
answers
137
views
Definition in some old paper about formal power series (automata theory) Part 2
I now know that $K \langle A \rangle$ is the set of all formal power series with finite support for some alphabet $A$ and field $K$. Now I have another question.
Later this expression comes up $\...
- 11
0
votes
0
answers
75
views
Definition in some old paper about formal power series (automata theory)
I have a question about a term in a paper about formal power series. It was never defined but the author used $K \langle A \rangle$, what set is $K \langle A \rangle$? Here $K$ is a field (commutative ...
- 1
2
votes
0
answers
51
views
Applying Angluin's automata learning to build Tree Automata
I have two different questions: a broad question (Q1) and a specific question (Q2).
Q1: Is there any established or well-accepted mechanism to learn tree automata based on Angluin's style of learning ...
- 21
11
votes
1
answer
165
views
Check whether DFA accepts majority of words less than a cutoff with another DFA
Question
Let $M$ be some DFA that reads integers in base $k$. Does there always exist some other DFA $M'$ that also reads integers in base $k$, where $M'(x)$ accepts if and only if $M$ accepts the ...
- 1,204
1
vote
1
answer
65
views
What is region construction in timed automata?
I've recently started self-learning timed automata.
There's this theorem in there that a timed automaton can be converted to a DFA using a "region" construction. I've looked up references on ...
- 125
4
votes
1
answer
96
views
Is there any context-free language that is inherently ambiguous as an indexed language
Indexed languages are defined as being produced by indexed grammar.
Is there any context-free language that is inherently ambiguous as an indexed language? That is, is there a context-free language ...
- 101
5
votes
1
answer
106
views
Is there any inherently ambiguous indexed language?
Indexed languages are defined as being produced by an indexed grammar.
My question is: Is there an indexed language such that there is no indexed grammar that can produce every word of the language in ...
- 101
3
votes
1
answer
205
views
Most non-deterministic automaton
My question is about how to construct, given a number n, an NFA with n states which gets converted to a complete (i.e., with no omitted transitions) DFA with exactly $2^n$ reachable states (even ...
- 141
11
votes
1
answer
286
views
Existence of injective length-preserving rational function to a smaller alphabet
(This is a simpler rephrasing of an earlier question I have since deleted.)
Definitions
For this question, a finite-state transducer is like a standard NFA, except at each transition, the transducer ...
- 1,204
4
votes
1
answer
137
views
Characterization of lengths of words accepted by DFAs
Let $M$ be an arbitrary DFA. For each $n \in \mathbb{N}$, let $f_M(n)$ be the number of words of length $n$ accepted by $M$. Then, consider the set of all such $f_M$ for all DFAs $M$.
Is there a nice ...
- 1,204
-1
votes
1
answer
92
views
What set of sequential 2-bit inputs would it take for any system with 2 bits of memory to not be able to know it is not being tested?
In a computer game, a player is tasked with making a sequential circuit that takes two one-bit inputs (for a total of four combinations) and outputs a bit depending on both the current input and the ...
- 99
2
votes
0
answers
79
views
Nondeterministic polynomial time languages with linearly bounded certificates
Define the class $X$ of languages by the condition that a language $L$ over alphabet $\Sigma$ is in $X$ iff there are a constant $c > 0$ and a polynomial-time checking relation $R$ such that for ...
- 191
0
votes
1
answer
178
views
Where to read about PSO (partial store order) memory model
I have been reading about TSO (total store order) memory models for concurrent programs, but I can not find resources for PSO (partial store order) memory models. Can someone please point to resources....
1
vote
1
answer
136
views
Bounded non-emptiness intersection of deterministic context-free grammars
Let A and B be two determinstic context-free grammar, and let N be an integer: What's the complexity of deciding if the intersection of the languages accepted by A and B over all strings of length ...
- 11
5
votes
1
answer
171
views
Alternative to LBA for recognising context-sensitive languages
I've always felt that there's no "canonical" automata for recognising context-sensitive languages. Much like there's DFA for regular, PDA for context-free and Turing machines for RE.
I'm ...
9
votes
0
answers
106
views
Expressiveness of pushdown automata whose stack height sequence is unambiguous
I consider pushdown automata on an alphabet $\Sigma$, which are intuitively finite automata with a stack. Formally, a pushdown automaton $A = (Q, q_0, F, \Gamma, \Delta)$ is a finite set $Q$ of states,...
- 8,896
13
votes
1
answer
458
views
Complexity of NFA to DFA minimization with binary threshold
What is the complexity of the following problem?
Given an NFA $A$ and a number $k\in \mathbb{N}$ in binary encoding, does there exist a DFA $B$ with at most $k$ states such that $L(A)=L(B)$?
...
- 5,531
5
votes
1
answer
176
views
Regular Expressions that converts into unambiguous automata
Brüggemann-Klein and Wood (1992) proved that a certain kind of regular expressions, that they call “Deterministic Regular expressions”, when converted into automata using the Glushkov's Construction, ...
- 541
3
votes
1
answer
598
views
Determinising unambiguous automata without exponential blowup
Is it possible to determinise unambiguous finite automata without exponential blowup in the number of states? I think it should not be possible but I am unable to come up with counterexamples.
- 131
0
votes
1
answer
123
views
Complexity for universal Counter Machine with {0,1}-valued registers
Consider a universal $\{0,1\}$-$k$-counter machine where each of the $k$ registers has a value in $\{0,1\}$ (as opposed to any non-negative integer in the usual formulation), and there are states $q_1,...
- 1
2
votes
1
answer
152
views
Does a finite, polynomially-bounded CFG translate into a polynomially-bounded DFA?
We are given a family of context-free grammars $\{ G_1, G_2, G_3, ..., G_n, ...\}$ where each $G_n$ generates strings only of length $n$ and obeys other constraints specified below. We want to study ...
- 424
3
votes
2
answers
185
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 ...
- 1,588
16
votes
0
answers
424
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....
- 1,227