Skip to main content

Questions tagged [automata-theory]

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

Filter by
Sorted by
Tagged with
3 votes
0 answers
48 views

Complexity of minimizing the index of a subgroup of the free group

Let $\Sigma$ be a finite alphabet and $G$ the free group generated by $\Sigma$. Let $W$ be a finite subset of $G$. (Represented as a list of formal expressions of the form $a_1^{\pm 1}\ldots a_n^{\pm ...
Vanessa's user avatar
  • 2,181
2 votes
0 answers
66 views

Complexity of FirstMatch (Prefix Elimination) Operator for regular expressions

Consider the operator $\texttt{FirstMatch} : 2^{\Sigma^*} \to 2^{\Sigma^*}$ defined as follows: $$\texttt{FirstMatch}(L) = \left \{ y \mid y \in L, \forall \text{ prefixes } x \text{ of } y, x \not \...
Agnishom Chattopadhyay's user avatar
5 votes
2 answers
203 views

The empty tree-word for regular tree languages

Are there references that consider the "empty tree-word" as an allowable element of regular languages of trees? Are there situations where it is more sensible to allow an empty tree-word? ...
TomKern's user avatar
  • 489
1 vote
0 answers
91 views

Planar Turing Machine with (relatively) Small Alphabet

There is a simple construction that takes any drawing of a Turing Machine in the plane and outputs another planar, equivalent one with a "small" blowup in the number of states, and only two ...
Ryan Dougherty's user avatar
4 votes
1 answer
144 views

Intersection Non-Emptiness for Two-Way Finite Automata

We know that checking the emptiness of intersection of an unbounded number of deterministic finite automata is PSpace-complete, and that just the emptiness problem for a nondeterministic two-way ...
A. G.'s user avatar
  • 43
2 votes
0 answers
81 views

Im looking for papers to read to strengthen my understanding of overall cs theory

I took automata theory and the things we learn in that class interest me a lot and am looking to read more papers to take a deeper dive into cs theory if any of y'all have any paper suggestions that ...
Emre Guzelordu's user avatar
4 votes
0 answers
106 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
5 votes
2 answers
152 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
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 ...
generic_logician's user avatar
1 vote
0 answers
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 ) ...
Coping Forever's user avatar
10 votes
5 answers
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#...
TomKern's user avatar
  • 489
3 votes
1 answer
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 ...
TomKern's user avatar
  • 489
0 votes
1 answer
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 ...
Rahul Gopinath's user avatar
2 votes
1 answer
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 ...
Rahul Gopinath's user avatar
8 votes
3 answers
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 ...
Satwik's user avatar
  • 181
2 votes
0 answers
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 ...
TomKern's user avatar
  • 489
7 votes
1 answer
220 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
257 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
361 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
497 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
  • 14.1k
6 votes
0 answers
80 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
311 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
69 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
69 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
1 answer
229 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
162 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
8 votes
1 answer
379 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,677
1 vote
0 answers
132 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
91 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
154 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
99 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
133 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
120 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
  • 489
3 votes
0 answers
126 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
77 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
4 votes
1 answer
200 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
6k 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
5 votes
0 answers
81 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
  • 489
6 votes
1 answer
289 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
436 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
153 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,049
1 vote
0 answers
97 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
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 ...
user1868607's user avatar
  • 1,049
3 votes
1 answer
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 ...
Janmar's user avatar
  • 135
1 vote
0 answers
138 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
53 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
177 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
96 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
  • 135
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

1
2 3 4 5
9