Questions tagged [automata-theory]

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

Filter by
Sorted by
Tagged with
7
votes
1answer
134 views

Random Deterministic Automata

I am familiar with the term of random graphs, such as $G(n,p)$- a distribution over simple undirected graphs with $n$ vertices, where each edge appears in a graph w.p. $p$. That is, each graph $G=(V,E)...
1
vote
1answer
110 views

Set of languages that can represent every c. e. languange

Could we find any set of languages $S$, such that it can represent every c. e. languange as it's union, intersection, complement, production(times of element ), and $S\subset X$, where $X\subseteq c.e....
3
votes
1answer
68 views

Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?

Suppose $L$ is a computably enumerable language, can it be decompose into infinite CFLs with infinite words ? $$L=\bigcup_{L_i\in CFL }^{\infty}L_i$$ Second question: if it is possible that every $L$...
-1
votes
1answer
75 views

Is there an inherently ambiguous language which can not be recognized by Deterministic LBA?

Is there inherently ambiguous language which can not be recognized by Deterministic LBA? For example, $L=\{wv: w,v=(x|y)^*, w=w^R,v=v^R\}$, is there any deterministc LBA that recognizes $L$ ?
1
vote
0answers
457 views

Equality Constraints over Sets with Tree Automata

Tree Automata can be used to model sets of values of a Herbrand Universe, for example, to model possible values in a functional program. Systems of subtype constraints over set expressions have ...
5
votes
1answer
191 views

What is the motivation behind defining Deterministic Looping Automata?

I was wondering about what could possibly be the motivation behind defining the deterministic looping automata? What puzzles me is that they accept a word iff they have a run on it! I believe they ...
2
votes
1answer
216 views

Deformation of finite regular languages [closed]

Let $L \subseteq \{0,1\}^n$ be any finite regular language s.t it has an acyclic DFA. Let $C$ be some class of acyclic DFAs. Let $\sigma \in S_n$ be a permutation on $n$ symbols. We can apply $\...
4
votes
1answer
1k views

Is Hartmanis-Stearns conjecture settled by this article?

The paper "On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited" by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec https://arxiv.org/abs/1601....
9
votes
3answers
270 views

Class of languages recognizable by single-tape 3-state TMs

I have for a while been curious about Turing Machines with exactly one tape and exactly 3 states (namely the start state $q_0$, the accept state $q_{accept}$, and the reject state $q_{reject}$). Note ...
1
vote
0answers
84 views

Relation between MDPs and non-deterministic finite automatons

I'm confused as to the relation (computability-wise) between markov decision processes and NFAs. Are finite state MDPs expressible as regular grammars? If so, are markov decision processes thus ...
1
vote
0answers
100 views

Convenient forms of Turing machines

Let us suppose that I have defined a new convenient form of the Turing machine for processing of some specific sort of commonly used structures. This form of TM contains some specific features ...
6
votes
1answer
427 views

Pumping Lemma over 2 way Automaton

Pumping Lemma essentially implies that for a NFA $N$ having $N_0$ states over a unary language $L_0$ any string belonging to $L_0$ can be obtained by 'pumping' one of the strings that have a length ...
6
votes
1answer
223 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
250 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
59 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
591 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$ : ...
7
votes
1answer
174 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
195 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
907 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 ...
7
votes
2answers
507 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
268 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
434 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
142 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
248 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
328 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
168 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
244 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
175 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
179 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
531 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
89 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
51 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
106 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
223 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
427 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
149 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
157 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
82 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
66 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
647 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, ...
6
votes
2answers
131 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
174 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
581 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
370 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
609 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
307 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 \...
42
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 ...