2022 Developer Survey is open! Take survey.

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
75 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 ...
user avatar
  • 91
0 votes
0 answers
19 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....
user avatar
4 votes
0 answers
154 views

Compressing one tape of a finite state transducer

Definitions A multitape one-way non-writing finite state automaton (MONA) introduced in 1 is an NFA that reads from multiple tapes at once and recognizes a relation over its alphabet(s) using accept/...
user avatar
  • 580
1 vote
1 answer
87 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 ...
user avatar
5 votes
1 answer
152 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 ...
user avatar
9 votes
0 answers
86 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,...
user avatar
  • 7,350
13 votes
1 answer
300 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)$? ...
user avatar
  • 5,246
5 votes
1 answer
137 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, ...
user avatar
  • 521
3 votes
1 answer
578 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.
user avatar
0 votes
1 answer
113 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,...
user avatar
  • 1
2 votes
1 answer
145 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 ...
user avatar
  • 414
3 votes
2 answers
126 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 ...
user avatar
  • 1,112
14 votes
0 answers
279 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....
user avatar
  • 1,095
6 votes
1 answer
164 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, ...
user avatar
  • 4,721
3 votes
1 answer
100 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 ...
user avatar
2 votes
0 answers
82 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 ...
user avatar
  • 193
4 votes
1 answer
447 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)$. ...
user avatar
2 votes
1 answer
183 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$ ...
user avatar
  • 12.5k
6 votes
1 answer
149 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 ...
user avatar
1 vote
1 answer
74 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 ...
user avatar
2 votes
1 answer
113 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 "...
user avatar
7 votes
2 answers
451 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}...
user avatar
  • 10k
4 votes
1 answer
147 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 ...
user avatar
  • 339
-1 votes
1 answer
237 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{...
user avatar
  • 157
7 votes
0 answers
100 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, ...
user avatar
  • 907
12 votes
0 answers
180 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 ...
user avatar
  • 7,350
1 vote
0 answers
38 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: ...
user avatar
3 votes
0 answers
99 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 ...
user avatar
7 votes
1 answer
211 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 ...
user avatar
9 votes
0 answers
92 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 ...
user avatar
  • 414
13 votes
1 answer
334 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 ...
user avatar
  • 321
9 votes
2 answers
351 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 ...
user avatar
1 vote
1 answer
150 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 ...
user avatar
  • 133
3 votes
1 answer
127 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^* ...
user avatar
9 votes
2 answers
627 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 $...
user avatar
  • 7,350
8 votes
0 answers
139 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 ...
user avatar
  • 181
3 votes
0 answers
134 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?
user avatar
6 votes
2 answers
514 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 ...
user avatar
5 votes
1 answer
173 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 ...
user avatar
  • 53
7 votes
1 answer
226 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 ...
user avatar
  • 1,947
3 votes
0 answers
89 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 ...
user avatar
  • 907
6 votes
1 answer
140 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 ...
user avatar
  • 5,246
3 votes
0 answers
93 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 ...
user avatar
8 votes
7 answers
1k 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 ...
user avatar
  • 1,947
1 vote
1 answer
74 views

Palindrome language and Finite Automata Machines [closed]

I'm a grad student in math. I'm unaware of available literature in theoretical computer science, so require suggestions for books. Here are the two topics I'm interested in exploring. 1) A complete ...
user avatar
9 votes
1 answer
192 views

Containment problem of an acyclic NFA in an NFA

Let $A$ and $B$ be NFAs, such that $A$ is acyclic. In the general case, deciding whether $L(A)\subseteq L(B)$ is $PSPACE$-hard. However, since $A$ is acyclic, we know that for every $w \in L(A)$, it ...
user avatar
  • 93
10 votes
3 answers
883 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 ...
user avatar
  • 907
8 votes
4 answers
625 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 ...
user avatar
  • 992
4 votes
1 answer
420 views

Are endmarkers necessary for Deterministic Pushdown Automata?

In the book by Kozen (Automata and Computability), the transition function of deterministic pushdown automata (DPDAs) is supposed, in contrast with non-deterministic pushdown automata (NPDAs), to ...
user avatar
10 votes
1 answer
655 views

What class of languages is recognized by finite-state automata with $k$ heads?

A DFA or NFA reads through an input string with a single head, moving left-to-right. It seems natural to wonder about finite-state machines that have multiple heads, each of which moves through the ...
user avatar
  • 842

1
2 3 4 5
8