Questions tagged [automata-theory]

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

6
votes
1answer
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 ...
9
votes
1answer
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 ...
2
votes
1answer
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 \}$ ...
1
vote
2answers
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 ...
8
votes
1answer
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$ : ...
6
votes
1answer
167 views

Automata : Language Containment, Minimality & Graph Homomorphism

Given two DFAs $A$ and $B$ defined on the same alphabet, a (graph) homomorphism $h:A \rightarrow B$ from $A$ to $B$ is a mapping of the states of $A$ into the states of $B$ such that : if the state $...
9
votes
1answer
194 views

Automata recognizing $X^*$ for a finite code $X$

Let $\Sigma$ be a finite alphabet. A code $X$ over $\Sigma$ is a subset of $\Sigma^*$ such that each word in $X^*$ can be uniquely represented as a concatenation of words in $X$. A code $X$ is finite ...
16
votes
1answer
905 views

Quadratic relationship between nondeterministic and deterministic space?

Savitch's theorem shows that $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$ for all large enough functions $f$, and proving that this is tight has been an open problem for decades. Suppose ...
6
votes
2answers
455 views

In the context of regular languages, must the alphabet be finite?

In The Theory of Parsing, Translation, and Compiling, Volume I, Section 0.2.1 (p.15 / 1972), Aho and Ullman casually write that "[a]n alphabet need not be finite or even countable, but for all ...
9
votes
2answers
263 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 ...
2
votes
1answer
77 views

CFGs in a certain normal form

Consider Context-Free Grammars with rules of the form $S\to\epsilon$ or $A\to aB | Ba|a$, meaning that any nonterminal other than $S$ can be replaced by a terminal, or by a pair of letters exactly one ...
7
votes
1answer
394 views

Shortest string in the intersection of a context-free language and a regular language

For a language $X$, define $ss(X) = \min_{x\in X} |x|$, the length of the shortest string in $X$. For simplicity, we define $ss(\emptyset)=0$. Let $L$ be a context-free language generated by a context-...
5
votes
0answers
139 views

Mastery-based grading for Theory of Computation

I would be interested to learn of anyone's experience using mastery-based (or "mastery-level") grading in a Theory of Computation course. Usually this requires—at a minimum— a detailed ...
2
votes
1answer
229 views

Partition refinement in transition state systems (bisimulation contraction)

I am trying to understand bisimulation contraction of Kripke models. I have read these lecture slides and this Wikipedia page, but I still don't fully understand it. I can understand that the two ...
7
votes
1answer
275 views

Is this a regular relation?

I'm a linguist (and not a computer scientist!) investigating a new sort of linguistic formalism for mapping phonological strings into other strings - and I'm wondering if it's a regular relation that ...
1
vote
0answers
164 views

Hysteresis in finite automata

The concept of hysteresis seems well suited to describe and distinguish finite automata: "Hysteresis is the dependence of the state of a system on its history." (Wikipedia, Hysteresis) "[The ...
17
votes
2answers
236 views

A reference for a “more algebraic” approach to pushdown automata and CFLs?

In the Sakarovitch's book on automata theory, it is written in the introduction to the section on rationals in the free group that the material presented therein lays "the foundation of a truly ...
6
votes
2answers
170 views

Finite Automata with succinct representation of chains of states

Consider a kind of automata similar to common DFAs or NFAs where it is possible to represent succinctly linear chains of states. In other words, an automaton like this: could be represented in this ...
3
votes
0answers
164 views

Formal definition of Turing Completeness [closed]

Wikipedia states: In computability theory, a system of data-manipulation rules […] is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing ...
14
votes
4answers
485 views

Hierarchies in regular languages

Is there any known "nice" hierarchy $L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$ (may be finite) inside the class of regular languages $L$? By nice here, the classes in each hierarchy capture ...
3
votes
1answer
74 views

Size bound on Büchi automaton for complement

For a given Büchi automaton $\mathcal A = (A, Q, \delta, q_0, F)$ we define a congruence on $A^{\ast}$ by $$ \begin{array}{llll} u \sim_{\mathcal A} v & :\Leftrightarrow & \mbox{for all }s,s' ...
2
votes
1answer
50 views

Determining the Class of a given Cellular Automata structure

Is it possible to write an algorithm that can determine the class of a given cellular automata structure ? (ie. Wolfram's 4 Classes) Thank you Ricky
1
vote
0answers
99 views

Why is an automaton on finite words co-deterministic iff its transitions are co-deterministic

In the article Automata and semigroups recognizing infinite words an automaton is specified by $\mathcal A = (Q, A, E, I, F)$ where $I$ is a set of initial states and $F$ a set of final states, $Q$ ...
2
votes
2answers
210 views

Simplest Machine Model for a langauge $ L = \{(w\# )^{k}\;|\; w\in \Sigma^{*},\;k\in \mathbb{N}\}$

What is the simplest machine model accepting the following language? $$ L = \{(w\# )^{k}\;|\; w\in \Sigma^{*},\;k\in \mathbb{N}\}$$ In other words, $L$ is obtained by taking each string $w$ in $\...
7
votes
3answers
400 views

Where does the modern canonical version of the Turing machine come from?

Turing's original 1936 description of his a-machine differs in several respects from the Turing machine I studied at university, leading me to questions: The Turing machine I learned about was ...
0
votes
0answers
148 views

Questions about the definition of the Quantum Turing Machine

I am trying to have a better understanding of the definition of the Quantum Turing Machine. My questions: If the output of a quantum program is the eigenvalue of the ground state of a Hamiltonian ...
3
votes
2answers
155 views

A property of suffix-free regular languages of maximal state complexity for the reverse operation

Let $L$ be a regular suffix-free language whose complete minimal automaton has $n$ states and that the minimal automaton of $L^R$ has exactly $2^{n-2}+1$ states. Let $p, q$ be two distinct states of ...
2
votes
0answers
77 views

Proof of the equivalence of Muller automata and Parity (or Rabin chain) automata

Let $A$ be some finite alphabet and $\mathcal A = (Q, \delta, q_0)$ be some determinisitic finite automaton. Then $\mathcal A$ accepts infinite words $\xi \in A^{\omega}$ according to the Muller ...
3
votes
0answers
65 views

A question on the introduction of the Wagner hierarchy from K. Wagner's original paper

My question is related to the seminal paper On $\omega$-regular sets by K. Wagner, which introduced a hierarchy which is now know as the Wagner- (or Wadge-) hierarchy of $\omega$-regular sets. In ...
13
votes
3answers
1k views

On the realisation of monoids as syntactic monoids of languages

Let $L \subseteq X^{\ast}$ be some language, then we define the syntactic congruence as $$ u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L $$ and the quotient ...
15
votes
2answers
611 views

Is there a well-defined division operation on finite automata?

Background: Given two deterministic finite automata A and B, we form the product C by letting the states in C be the cartesian product of states in A and states in B. Then, we choose transitions, ...
5
votes
2answers
124 views

Characterization of union of DCFLs

We know that DCFL is not closed under the union operation and CFL is closed under union and contains the union of DCFLs. Is there a characterization of finite unions of DCFLs?
5
votes
1answer
170 views

Useful equivalence relations on $X^{\ast}$ (like the Nerode and syntactic equivalence relations)

I want to have an overview of all the meaningful equivalence relations defined on $X^{\ast}$, in particular when the languages in question are regular. They typically arise in connection with the ...
2
votes
1answer
527 views

Kleene closure of DFA

Given an $n$-state DFA (over a binary or any fixed alphabet), what is the complexity of computing its Kleene closure DFA? What is the largest possible/known blow-up in the number of states?
21
votes
1answer
354 views

For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?

It is well known that the following problem is PSPACE-complete: Given regular expression $\beta$, does $L(\beta) = \Sigma^*$? What about determining equivalence to other (fixed) regular ...
2
votes
3answers
542 views

Current research topics in tree automata

What are current research topics connected with tree automata? I'm particularly interested with connection between automatas, logics and databases. Kind regards, XYZ
5
votes
2answers
285 views

Simplest Machine Model Accepting $L = \{ww^Rw\;|\; w\in \Sigma^*\}$

Let $\Sigma$ be a finite alphabet. A trivial finite automaton can accept the language $L_1 = \{w\;|\;w\in \Sigma^*\}$. A simple pushdown automaton can accept the language $L_2 = \{ww^R\;|;w\in \...
41
votes
10answers
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 ...
3
votes
1answer
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? ...
2
votes
0answers
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, ...
12
votes
1answer
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. ...
1
vote
1answer
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 ...
14
votes
1answer
541 views

Novel proof of pumping lemma for regular languages

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\...
1
vote
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 "...
7
votes
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^*$ ...
1
vote
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 ...
9
votes
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 ...
3
votes
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 ...
14
votes
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{...
9
votes
2answers
271 views

Generalizing Brzozowski's DFA minimization algorithm to finite automata with different classes of accepting states?

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 ...