Questions tagged [automata-theory]

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

324 questions
222 views

Has there been a study of circuits operating on arrays?

Much ink has been spilled studying the theory surrounding computation by combinatorial circuits operating on bits or boolean values - with AND, OR and NOT gates (as those are enough to implement any ...
230 views

Transition monoid membership for DFAs

Given a complete DFA $A=(Q, \Gamma, \delta, F)$, we can define a collection of functions $f_a$ for each $a\in \Gamma$and with $f_a:Q\rightarrow Q$, $f_a(q)=\delta(q, a)$. We can generalize this notion ...
80 views

Giving a finite collection of infinite words “complex” enough with respect to automata measure

We consider acceptance by Büchi automata. Let $X = \{0,1\}$ and $X^{\mathbb N}$ the set of all infinite sequences. Then for each $n$ do we have a finite collection $\{ \xi_1, \xi_2, \ldots, \xi_k \}$ ...
56 views

Algorithms to synthesize optimal plans satisfying temporal logic constraints

I know how NuSMV can be applied on a model to check if certain temporal logic statements are satisfied, particularly LTL. I also know of the LTL to BA conversion routines available online. I am ...
506 views

NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?

Given a NFA $N$ and its equivalent DFA $D$ resulting from the total determinization of $N$ (using powerset construction, for example), the following properties hold for $N$, $D$ and for any word $w$ : ...
167 views

15k views

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Real computers have limited memory and only a finite number of states. So they are essentially finite automata. Why do theoretical computer scientists use the Turing machines (and other equivalent ...
100 views

What is the simplest universal unidimensional interaction net system?

The Interaction Combinators are possibly the simplest multidimensional system of interaction nets that is Turing-complete. What about interaction nets with only 2 ports - 1 principal, 1 auxiliary? ...
72 views

What is the class of the languages recognized by PCREs?

I have been considering building a tool that would convert regexes between the various syntaxes (BRE, ERE, PCRE). It is obvious that PCREs are too strong for the is-regular problem to be decidable, ...
196 views

Is there a survey of the field of quantum automata?

I'm looking for a survey paper of the important concepts in the field of Quantum Automata. I've found Quantum Automata Theory -- A Review by Hirvensalo, but it sounds too succinct to grasp the topic. ...
355 views

How to generate Extended Finite State Machines Randomly with some properties?

This is related to my academic project An extended finite state machine is a tuple $SM=(I,S,T)$ (simplified): $I$ is the set of identifiers and it's divided into two sets Inputs and outputs, for ...
Let $\mathcal{L}$ be the family of all languages over $\Sigma$ satisfying the pumping property of regular languages. Namely: for each $L\in\mathcal{L}$, there is an $N\in\mathbb{N}$ s.t. every word $w\... 2answers 146 views Are equalizers of regular functions always regular languages? (My guess is no because PCP, but…) Edit: I originally defined a regular function as a function computable by a Mealy machine, but Denis pointed out that that was a weaker model than what I was thinking of. So to be more precise, by a "... 1answer 138 views A word anticorrespondence problem A problem instance is a finite list of 4-tuples$(\alpha_1, u_1, v_1, \beta_1), ..., (\alpha_N, u_N, v_N, \beta_N)$, where$\alpha_i, \beta_i \in X$come from a finite set, and each$u_i,v_i \in A^*$... 1answer 100 views Normal form for deterministic (sub)sequential transducers with letter-by-letter outputs For a project I'm working on, it would seem useful to have a normal form for deterministic (sub)sequential transducers in which the set of states,$Q$, is partitioned into states,$r \in Q_R$, that ... 1answer 168 views Do bounded-visit nondeterministic linear bounded automata recognize only regular languages? Do bounded-visit nondeterministic linear bounded automata recognize only regular languages? By a nondeterministic linear bounded automaton (nLBA) I mean a single-tape nondeterministic Turing machine ... 1answer 69 views An exponentially-ambiguous weighted automaton without an equivalent polynomially-ambiguous automaton A min-plus weighted automaton (WFA) is a nondeterministic automaton with a weight function that assigns each transition a weight in$\mathbb{N}$. The weights along a run are summed, and the value of a ... 2answers 556 views Regular versus TC0 According to the Complexity Zoo,$\mathsf{Reg} \subseteq \mathsf{NC^1}$and we know that$\mathsf{Reg}$cannot count so$\mathsf{TC^0} \not\subseteq \mathsf{Reg}$. However it doesn't say if$\mathsf{...
Brzozowski's algorithm for converting a DFA into an equivalent minimum-state DFA is remarkably simple: if $R(D)$ denotes the NFA formed by reversing all the edges in a DFA $D$, making the old start ...