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
1answer
554 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.
0
votes
1answer
97 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,...
2
votes
1answer
131 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 ...
7
votes
1answer
562 views

Is it known if $\mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))$?

$\mathrm{CFL}$ is the class of context-free languages. Question Is $\mathrm{CFL}$ known to be solvable in $o(log^{2}(n))$ non-deterministic space? What about $\mathrm{DCFL}$?
7
votes
1answer
209 views

Languages whose Parikh image is recognizable

Let $\Sigma$ be some alphabet, and $p : \Sigma^* \to \mathbb N_0^{|\Sigma|}$ the Parikh map. A formal language $L \subseteq \Sigma^*$ is called a slip-language, if $p(L)$ is a semilinear set. By ...
2
votes
2answers
109 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 ...
8
votes
7answers
868 views

NP-complete decision problems on deterministic automata

Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or ...
13
votes
0answers
255 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....
9
votes
2answers
557 views

Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?

Fix a deterministic finite automaton $A$ defining a regular language on the alphabet $\Sigma = \{0, 1\}$, and call the (Hamming) weight of a word $w \in \Sigma^*$ its number of $1$'s. Given a length $...
6
votes
1answer
159 views

Is the function $f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$ regularity-preserving?

A function $f: A^* \to A^*$ is regularity-preserving if, for each regular language $L$ of $A^*$, the language $f^{-1}(L)$ is regular. I think I have a proof, as a consequence of more general results, ...
3
votes
1answer
93 views

Conditioning Probability on a Language With Measure 0

Let $\Sigma = \{ 1, 2, \ldots, n\}$ be some alphabet. Assume that you have a coin with n-sides (each side corresponds to a letter in $\Sigma$), and we get each letter with equal probability. Now you ...
2
votes
0answers
73 views

Necessary and sufficient condition for an infinite tree to be context-free

A Buchi automaton is non-empty iff it accepts an infinite word of the form $uv^\omega$ (here $u,v$ are finite words). In other words, if $\{w\}$ is an $\omega$-regular language, then it is of that ...
4
votes
1answer
335 views

Can we efficiently convert from NFA to smallest equivalent DFA?

Definitions For any automaton $X$, let $L(X)$ denote the language recognized by $X$. For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$. ...
2
votes
1answer
144 views

DFSA and NFSA intersection problem

Given $k$ deterministic FSAs of $n$ states the intersection of their languages is empty is decidable in $n^{o(k)}$ time is an open problem. For unbounded $k$ it is known the problem is $PSPACE$ ...
6
votes
1answer
140 views

Random Cerny Conjecture

For simplicity, all DFAs will be using the binary alphabet $\{0,1\}$. Let $M$ be a synchronizable DFA. We let $p(M,n)$ be the probability that a random $x\in \{0,1\}^n$ will synchronize $M$. We define ...
1
vote
1answer
67 views

Definition of Rabin acceptance condition for omega automatons [closed]

I've been trying hard to understand something. According to wikipedia and this paper, the definition of the Rabin acceptance condition involves a set of pairs of states. I've been told that the left ...
4
votes
1answer
122 views

Decomposition of safety and liveness properties

In Alpern,Schneider 86 is described how to extract the automata that recognize safety and liveness properties from a Buchi automaton $m$. This shows that any property rapresented by a Buchi automaton ...
2
votes
1answer
88 views

NP-Completeness of Finding Minimum Automaton, in Gold's paper

I have been investigating "learning automatas", and I came across reference to Gold's papers several times: "Complexity Of Automaton Identification From Given Data", and "...
10
votes
2answers
378 views

Number of minimal DFAs of size at most $m$?

Let $\Sigma$ be an alphabet of size $2$, and consider minimal DFAs whose size is bounded by at most $m$. Let $f(m)$ denote the number of different such minimal DFAs. Can we find a closed-form ...
7
votes
2answers
446 views

Finite-State Automata over a real-valued alphabet

Consider a finite state set $Q$, with a distinguished start state $s\in Q$, as well as two functions: a transition function $\delta:Q\times\mathbb{R}\to Q$ and a final output function $F:Q\to\mathbb{R}...
-1
votes
1answer
128 views

What is the time complexity of computing intersection and union of Nondeterministic Finite Automata (NFAs)?

Assume that $\mathcal{A} = (Q_A, \Sigma, \Delta_A, q_{i_A}, F_A)$ and $\mathcal{B} = (Q_B, \Sigma, \Delta_B, q_{i_B}, F_B)$ are two NFAs. What is the worst-case time complexity of computing $\mathcal{...
14
votes
1answer
574 views

Minimizing residual finite state automata

Residual finite state automata (RFSAs, defined in [DLT02]) are NFAs that have some nice features in common with DFAs. In particular, there is always a canonical minimum sized RFSA for every regular ...
7
votes
0answers
99 views

Deciding whether DCFG is visibly pushdown

Is the following problem decidable? If so, what's the best algorithm known? Instance: a deterministic pushdown automaton $A$ Question: Does there exist (i) some partition of the alphabet into push, ...
9
votes
2answers
340 views

Bounds on this Strategy for Separating Words

Question Given binary string $z \in \{0,1\}^n$, let $f(z)$ be the smallest integer $k$ such that there exists a DFA with $k$ states, such that reading $z$ from a specific starting state, we end at a ...
14
votes
2answers
841 views

Büchi automata with acceptance strategy

The problem Let $A=\langle \Sigma, Q, q_0,F,\Delta\rangle$ be a Büchi automaton, recognizing a language $L\subseteq\Sigma^\omega$. We assume that $A$ has an acceptance strategy in the following sense :...
12
votes
0answers
172 views

Regular languages accepted by an automaton with at most one transition per letter

I'm interested in the (very restricted) subset of regular languages for which there is an automaton having the following property: for every letter $a$ of the alphabet, the automaton has at most one ...
1
vote
0answers
35 views

Nominal Tree Languages i.e. with Binders and Infinite Symbols?

I'm wondering if there has been any research done into automata that accept languages of trees that can bind arbitrary variables, and are considered equal under alpha equivalence. I've found so far: ...
3
votes
0answers
73 views

Deciding whether an arbitrary context-free grammar generates a deterministic push-down automata?

I know that it's undecidable whether an arbitrary context-free grammar is ambiguous, but is it decidable whether that grammar is deterministic? I can't find the answer to this question anywhere on the ...
13
votes
0answers
382 views

Can we approximate the number of words accepted by an NFA?

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete. The second ...
7
votes
1answer
165 views

Isomorphism of ‘ordered’ DAGs / acyclic semiautomata

I am wondering what is known about the isomorphism problem on ordered DAGs, in particular how to find a canonical representative modulo isomorphism. By ordered I mean that each vertex has a list of ...
9
votes
0answers
87 views

Reference request: DFA linear-time minimization

What is the most complicated kind of deterministic finite-state automaton that can be minimized in $O(n)$ time? Here’s what I’ve been able to find so far: The acyclic case has been solved. So any ...
21
votes
2answers
3k views

computing the minimal NFA for a DFA

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known ...
11
votes
1answer
191 views

Planarity of planar finite automata intersection

It was shown that any regular language can be specified by planar $\varepsilon$-free nondeterministic finite automaton (Bezáková, Ivona, and Martin Pál. "Planar finite automata."). Is it ...
3
votes
1answer
120 views

Rewrite relations - proof of correctness

Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular relation. We define the obligatory rewrite relation over $T$ as follows: $$ R^{obl}(T) := N(T) \cdot (T \cdot N(T))^* $$ $$ N(T) := Id(\Sigma^* ...
4
votes
1answer
126 views

Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata

Let $\mathcal A$ be an automaton, then I define the following $\omega$-language accepted by $\mathcal A$: $$ L'(\mathcal A) := \{ \eta \in X^{\omega} : v \sqsubset \eta \mbox{ implies } v \in L(\...
6
votes
0answers
191 views

Separation of the states of a deterministic omega-automaton by looping words taken from a regular language of non-empty words

Consider a deterministic transition structure having states in set $X$ and transition function $\rightarrow$, and an initial state $x \in X$. This structure is intended to be part of an automaton ...
2
votes
0answers
206 views

Complexity of DBA-recognizable Omega-Languages

Given an $\omega$-regular expression $r$, how difficult is it to decide if $L(r)$ is recognizable by some deterministic Büchi automaton? I know it is solvable in EXPTIME by converting the regular ...
1
vote
1answer
136 views

What kind of computational model is the brain? [duplicate]

I was wondering what kind of computational model is the human brain (as it seems superior to a Turing machine). Another thing that should be a separate question, What would be a perfect computer model ...
8
votes
0answers
132 views

Determining if transducer automaton has two states with intersecting images, without minimizing?

I work (in implementation!) with deterministic finite state automata with input and output; i.e. there are transitions (start state,input letter)$\to$(new state,output letter). Thus every state gives ...
8
votes
4answers
560 views

Constraints on sliding windows

Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer. I would like to know if anything is known on the time and space complexity with respect to $n$ to check for ...
-2
votes
1answer
371 views

Can I show algebraically that this regular expression accepts all binary strings?

The task is to prove that (0+1)* and 0*(1.0*)* are equivalent. 1. http://rubular.com/r/K9Hp9tU6px 2. http://rubular.com/r/N8VpoEcch4 EDIT: Forgot that + was ambiguous here! I want to prove that the ...
3
votes
0answers
132 views

Weakest model of computation that can typecheck?

What's the weakest (known) model of computation (or smallest language class) that can decide whether a simply-typed lambda calculus program type checks? What about an (explicitly typed) CoC program?
6
votes
2answers
364 views

2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata

How can I convert a 2DFA to a normal DFA. Is there an algorithm/elegant way to do that ? I've been researching this for a few days but I coundn't find anything. Actually I want to implement that in ...
5
votes
1answer
165 views

Is there any equation-based method for transforming Büchi-automata to omega-regular language?

I know there exists an equation-based method for transforming finite automata into regular language (or `regular expression'). The main idea is as follows. First we construct a set of equations ...
7
votes
2answers
251 views

Closure of Recognizable Languages under Kleene Star: Algebraic Proof?

Let $Rec(\Sigma)$ be the class of languages over $\Sigma^*$ recognizable by finite monoids. To show that $Rec(\Sigma)$ is closed under Kleene star, one would usually refer to the equivalence of ...
5
votes
1answer
241 views

Name for a special family of languages?

I was wondering whether there is a standard name in the literature for the following family $\mathcal{F}$ of languages over any finite alphabet $\Sigma = \{a_1,\ldots,a_k\}$: $\mathcal{F}$ consists ...
10
votes
3answers
741 views

Maximum shortest word accepted by pushdown automata

Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ...
6
votes
1answer
111 views

What is the minimal class of subshifts for which conjugacy is known to be undecidable?

The question of whether two finite one directional shifts are conjugates is known to be decidable. The same question for sofic shifts is famously open. I have seen that some works manage to prove ...
3
votes
0answers
78 views

Incremental PDA emptiness testing?

Is there anything known about the problem of incremental emptiness testing for a pushdown automata? Suppose you have a PDA with (up to) $n$ states and transitions, but instead of being given the ...
2
votes
0answers
71 views

Proof: Why are MM-1QFA strictly more powerful than MO-1QFA? // Quantum automata

While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97). More ...

1
2 3 4 5
8