Questions tagged [automata-theory]

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

Filter by
Sorted by
Tagged with
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})$. ...
domotorp's user avatar
  • 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, ...
gsv's user avatar
  • 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 ...
user avatar
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, ...
The Pointer's user avatar
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 ...
Vetrivel's user avatar
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, ...
Abced Decba's user avatar
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 ...
Rémi's user avatar
  • 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 ...
a3nm's user avatar
  • 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
user69786's user avatar
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}^+$. ...
Hanshika's user avatar
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. ...
bb94's user avatar
  • 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 ...
jfriemel's user avatar
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 ...
Thomas Tappeiner's user avatar
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. ...
TomKern's user avatar
  • 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 ...
Nicola Gigante's user avatar
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 ...
timtombobjohn's user avatar
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 ...
tchappy ha's user avatar
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....
QMath's user avatar
  • 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, ...
voltas1231's user avatar
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 ...
TomKern's user avatar
  • 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$ ...
Nicola Gigante's user avatar
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 ...
user1868607's user avatar
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 ...
user3508551's user avatar
  • 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 ...
user1868607's user avatar
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)$, $\...
NathanLiitt's user avatar
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 ...
user1868607's user avatar
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 ...
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
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 ...
Tim's user avatar
  • 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 ...
ylee's user avatar
  • 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 ...
Jake's user avatar
  • 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 ...
whoisit's user avatar
  • 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 ...
WangAtChicago's user avatar
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 ...
WangAtChicago's user avatar
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 ...
user6767509's user avatar
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 ...
Jake's user avatar
  • 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 ...
Jake's user avatar
  • 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 ...
Nic's user avatar
  • 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 ...
Alberto's user avatar
  • 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....
Anonymous's user avatar
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 ...
RockyBilboa's user avatar
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 ...
William Turner's user avatar
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,...
a3nm's user avatar
  • 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)$? ...
Shaull's user avatar
  • 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, ...
ricardorr's user avatar
  • 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.
Arka's user avatar
  • 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,...
RRRR's user avatar
  • 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 ...
ShyPerson's user avatar
  • 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 ...
Nicola Gigante's user avatar
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....
M.Monet's user avatar
  • 1,227

1
2 3 4 5
9