Questions tagged [automata-theory]

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

Filter by
Sorted by
Tagged with
2 votes
0 answers
51 views

Higher dimensional automata?

An NFA is just the data of a labelled, directed multigraph with a accepting predicate over the vertices. Simplicial sets generalize directed multigraphs by allowing the existence of higher dimensional ...
Steven Schaefer's user avatar
3 votes
1 answer
65 views

Modify DCFG to enforce length limit

Given a deterministic context-free grammar $G$ that generates the language $L$, is there an efficient algorithm that can be used to construct another DCFG $G_N$ that generates the language $\{ s \in L ...
Jerry Ding's user avatar
6 votes
0 answers
106 views

How to prove clock equivalence is a time-abstracted bisimulation

An important step of developing the theory of timed automata is to reduce the question of reachability in the timed automata, which has infinitely-many states, to the question of reachability in an ...
generic_logician's user avatar
1 vote
0 answers
41 views

Constructing a DFA with $n$ states for which $L*$ needs $n$ equivalence queries

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
Coping Forever's user avatar
10 votes
5 answers
280 views

Obscure characterizations of the regular languages

I've been collecting equivalent characterizations of the regular languages. Does anyone know of any I haven't yet found? Wikipedia has a bunch: https://en.wikipedia.org/wiki/Regular_language#...
TomKern's user avatar
  • 429
3 votes
1 answer
166 views

Is it useful to "untangle" an NFA by converting to a regular expression and back

Consider the following recursive algorithm for converting a regular expression into a transition diagram for an NFA with epsilon-edges (freely, optionally traversible edges), one start state and one ...
TomKern's user avatar
  • 429
0 votes
1 answer
76 views

What is the intution on the TTT algorithm for regular grammar inference?

This question is about the TTT algorithm for blackbox automata inference as defined in [1] and [2]. I am finding it difficult to understand all the innovations made by the algorithm. I understand how ...
Rahul Gopinath's user avatar
2 votes
1 answer
110 views

What is the current state of the art on exact identification of DFAs with a maximum N states

This is a question about the blackbox grammar inference of deterministic finite state automata (DFAs). In particular I want to ask about when one can exactly identify the target DFA using queries to ...
Rahul Gopinath's user avatar
8 votes
3 answers
322 views

Relationship between size of Boolean functions and DFAs

Are there any works that study the relationship between Boolean functions and the size of the minimal DFAs required to represent those Boolean functions? Boolean functions refer to the usual ...
Satwik's user avatar
  • 181
2 votes
0 answers
73 views

Is there a text that contains all 4 Büchi-Elgot-Trakhtenbrot-style theorems?

There are several natural Büchi-Elgot-Trakhtenbrot-style theorems: The equivalence of various finite automata on finite words and the weak monadic second order theory of 1 successor The equivalence ...
TomKern's user avatar
  • 429
7 votes
1 answer
217 views

Counting the different subsets of nodes seen when iterating a subset through a directed graph

For a given directed graph $G = (V, E)$ (possibly with loops), and some $S\subseteq V$ define the operation $G(S) = \{ v\mid (u,v)\in E\text{ for some } u\in S \}$. Now consider the infinite sequence $...
alsips-cl's user avatar
  • 158
7 votes
1 answer
253 views

Are regular expressions polynomially decomposable?

This question is related to my previous question (LINK). I would like to ask whether regular expressions can be polynomially decomposed in the following sense: A regular expression $\mathcal{R}$ is $...
Bartosz Bednarczyk's user avatar
10 votes
1 answer
332 views

The complexity of conversion from a regular expression to a nondeterminsitic automata and back after changing initial and final states

Suppose that a regular expression $\mathcal{R}$ over an alphabet $\Sigma$ is given. It is well-known that one can now construct a non-deterministic finite automaton $\mathcal{A}$ such that $\mathcal{R}...
Bartosz Bednarczyk's user avatar
6 votes
1 answer
490 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})$. ...
domotorp's user avatar
  • 14k
6 votes
0 answers
72 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, ...
gsv's user avatar
  • 421
2 votes
1 answer
291 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 ...
user avatar
0 votes
2 answers
67 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, ...
The Pointer's user avatar
0 votes
0 answers
66 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 ...
Vetrivel's user avatar
1 vote
0 answers
163 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, ...
Abced Decba's user avatar
7 votes
1 answer
156 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 ...
Rémi's user avatar
  • 262
7 votes
1 answer
347 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 ...
a3nm's user avatar
  • 9,269
1 vote
0 answers
122 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
user69786's user avatar
0 votes
0 answers
76 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}^+$. ...
Hanshika's user avatar
2 votes
1 answer
145 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. ...
bb94's user avatar
  • 123
4 votes
0 answers
94 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 ...
jfriemel's user avatar
6 votes
0 answers
126 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 ...
Thomas Tappeiner's user avatar
5 votes
1 answer
116 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. ...
TomKern's user avatar
  • 429
3 votes
0 answers
114 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 ...
Nicola Gigante's user avatar
0 votes
0 answers
69 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 ...
timtombobjohn's user avatar
0 votes
0 answers
185 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 ...
tchappy ha's user avatar
4 votes
1 answer
197 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....
QMath's user avatar
  • 303
13 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, ...
voltas1231's user avatar
4 votes
0 answers
77 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 ...
TomKern's user avatar
  • 429
6 votes
1 answer
284 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$ ...
Nicola Gigante's user avatar
2 votes
1 answer
427 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 ...
user3508551's user avatar
  • 1,153
3 votes
2 answers
134 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 ...
user1868607's user avatar
  • 1,017
1 vote
0 answers
94 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)$, $\...
NathanLiitt's user avatar
3 votes
3 answers
565 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 ...
user1868607's user avatar
  • 1,017
3 votes
1 answer
224 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 ...
Janmar's user avatar
  • 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 $\...
Tim567's user avatar
  • 11
0 votes
0 answers
80 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 ...
Tim's user avatar
  • 1
2 votes
0 answers
52 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 ...
ylee's user avatar
  • 21
11 votes
1 answer
175 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 ...
Jake's user avatar
  • 1,214
1 vote
1 answer
77 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 ...
whoisit's user avatar
  • 125
4 votes
1 answer
102 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 ...
WangAtChicago's user avatar
5 votes
1 answer
108 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 ...
WangAtChicago's user avatar
3 votes
1 answer
206 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 ...
user6767509's user avatar
11 votes
1 answer
288 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 ...
Jake's user avatar
  • 1,214
4 votes
1 answer
142 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 ...
Jake's user avatar
  • 1,214
-1 votes
1 answer
101 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 ...
Nic's user avatar
  • 99

1
2 3 4 5
9