Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
2
votes
1answer
68 views
Can a det. $k$-counter machine ($k \geq 2$) be simulated by a det. $k'$-counter machine using non-$\epsilon$-moves followed by $\epsilon$-moves?
I have a question concerning deterministic $k$-counter machines, for $k \geq 2$. Recall that in this context, the determinism is expressed by the fact that the machine can never face a choice between ...
2
votes
0answers
67 views
Characterization of deterministic pushdown automata
Is there any known characterization for deterministic pushdown automata (DPDA)?
For example, visibly pushdown automata(VPA) is a subclass of DPDA, which is characterized by following syntactic ...
1
vote
0answers
51 views
Rational power series over $\mathbb N \cup \{\infty\}$, rationality of singular part
Let $\Sigma$ be a finite alphabet, and consider the formel power series over $\Sigma$ considered as non-commuting variables with coefficients in the semiring $\mathcal N := \mathbb N \cup \{\infty\}$ ...
3
votes
1answer
78 views
“Combining” two mealy machines [closed]
How could you combine two mealy machines, the first one $M_1$ has as input $\sum_{1}^*$ and as output $\sum_{2}^*$,
the second machine $M_2$ uses the output $\sum_{2}^*$ as the input and outputs $\...
3
votes
3answers
96 views
Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$
Let $M$ be a monoid, the family of rational sets $\operatorname{RAT}(M)$ is defined as the smallest set containing the finite subsets, and closed under union, concatentaion and the star operation. The ...
9
votes
1answer
115 views
Generalisation of the statement that a monoid recognizes language iff syntactic monoid divides monoid
Let $A$ be a finite alphabet. For a given language $L \subseteq A^{\ast}$ the syntactic monoid $M(L)$ is a well-known notion in formal language theory. Furthermore, a monoid $M$ recognizes a language $...
-4
votes
1answer
37 views
Prove that L* is a regular language [closed]
Suppose that L is any language , not necessarily regular, whose alphabet is {0}; that is the strings of L consist of 0's only. Prove that L* is regular.
5
votes
1answer
91 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 ...
2
votes
1answer
227 views
Existence of an algorithm
I need to show that there exists a polynomial time algorithm that inputs a deterministic automata $A$, and decides if $A$ accepts a word w if and only if it also accepts any word obtained by permuting ...
6
votes
1answer
153 views
Finding a minimal DFA whose language has a desired intersection with another
Suppose I have regular languages $B \subseteq A$, with corresponding (known) minimal deterministic finite automata $M_A, M_B$.
I would like to find another regular language $C$ such that $B = A \cap ...
-1
votes
1answer
39 views
Push Down Automata [closed]
Can we put more than one element in stack at a time.
Actually I am asking that this transition function is valid for PDA:
∆(q,a,z)=(q',aaz)
Where:
q and q' are states
a is input symbol
z is starting ...
3
votes
0answers
83 views
Looking for a specific tree automata model
is there any tree automata model over unranked trees (that is with unbounded number of children for each node), such that:
Checking non-emptiness and universality is decidable in elementary time,
...
21
votes
2answers
460 views
Testing whether letters can be scheduled to achieve a word in a regular language
I fix a regular language $L$ on an alphabet $\Sigma$, and I consider the following problem that I call letter scheduling for $L$. Informally, the input gives me $n$ letters and an interval for each ...
4
votes
1answer
196 views
Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$?
$CFL$ is the class of context-free languages.
Question
Is $CFL$ known to be solvable in $o(log^{2}(n))$ non-deterministic space? What about $DCFL$?
-1
votes
1answer
86 views
When designing a DFA, am I allowed to design two separate Machines and perform an Intersection on them? [closed]
I am trying to design a DFA s.t. The set of strings in x ∈ {0, 1}∗
such that the number of zeros is a multiple of 3 and the number of one's is even.
My idea was to create two Machines M1 = (Q1, Σ, δ1,...
14
votes
1answer
693 views
Complexity of the problem of words with fewest distinct letters accepted by a finite automaton
Given a finite (deterministic or nondeterministic, I don't think this has much importance) automaton A and a threshold n, does A accept a word containing at most n distinct letters?
(By k different ...
13
votes
1answer
130 views
Regular language that discriminates between two deterministic CFGs
Suppose you are given two deterministic push down automata which recognize languages $A$ and $B$, and wish to determine whether there is a regular language $R$ such that $A \subseteq R$ and $R \cap B =...
7
votes
1answer
122 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)...
0
votes
0answers
43 views
Suffix automata on a queue
There is algorithm for computing suffix automaton of string $s$ by appending letters one by one and update the automaton which takes amortized $O(1)$. Is there a way to also support erasing of the ...
1
vote
1answer
96 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
60 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
69 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
455 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
156 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
208 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 $\...
5
votes
1answer
995 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....
0
votes
0answers
96 views
What are ordered automata?
recently my supervisor told me of ordered automata, however, I searched for material on the internet about them and did not find, could someone explain me what they are or recommend link with material ...
9
votes
3answers
255 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
55 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
96 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
399 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 ...
7
votes
1answer
217 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 ...
10
votes
1answer
181 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 ...
3
votes
1answer
79 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
50 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 ...
9
votes
1answer
435 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
154 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 $...
10
votes
1answer
190 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 ...
17
votes
1answer
894 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
327 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
251 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
75 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
331 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-...
6
votes
0answers
134 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
189 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 ...
8
votes
1answer
234 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
154 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
223 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 ...
7
votes
2answers
164 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
147 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 ...
