# Questions tagged [automata-theory]

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

433 questions
Filter by
Sorted by
Tagged with
48 views

• 163
121 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 ...
1 vote
45 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 ) ...
312 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#...
• 489
177 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 ...
• 489
87 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 ...
117 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 ...
342 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 ...
• 181
82 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 ...
• 489
220 views

• 1,337
361 views

714 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 ...
• 1,049
227 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
138 views

• 1,214
1 vote