Questions tagged [automata-theory]
Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
466 questions
8
votes
1
answer
172
views
Partial word completions with a factor compatible with another partial word
Consider the alphabet $\Sigma = \{0,1\}$ and words over $\Sigma$. A partial word is a word over the alphabet $\Sigma' = \{0, 1, ?\}$, i.e., a word with "holes" that can correspond to either ...
- 11.5k
5
votes
1
answer
152
views
Equivalent one-way alternating tree automaton of a given two-way alternating tree automaton
Is there an algorithm that returns an equivalent one-way alternating tree automaton of a given two-way alternating tree automaton?
TATA provides an example (7.6.4), but no algorithm is given.
Thanks!
- 51
0
votes
0
answers
33
views
Why do we need to “fix” a DPDA to force it to read the entire input and halt, if looping or early termination already implies rejection?
I am new to Theory of Computation. Kindly bear with my question rephrasing. I rephrased my question using chatgpt but, the following question is exactly what I wanted to ask
I have understood, DFA, ...
4
votes
0
answers
70
views
Linear size automaton for complement of domain of top-down tree transducer
I recently thought of the following simple fact which seems like the kind of thing that should have been proved in the 1970s, but I did not manage to find it in the literature. Is there any reference?
...
0
votes
0
answers
76
views
PDA with reset transitions, plain and probabilistic
Consider the PDAs with unary alphabets for both stack and for input. Test for empty stack is allowed, but not $\epsilon$-transitions. Now suppose we additionally allow for reset transitions, that can ...
- 101
12
votes
1
answer
403
views
Extending Fliess theorem to weighted automata over commutative semirings
I was working on a problem that turned out to be unexpectedly connected to weighted automata. Along the way, I encountered an independent but rather interesting question that I thought would be worth ...
- 261
3
votes
3
answers
378
views
Advanced texts in theoretical computer science
I'm finishing learning a course in Theoretical Computer Science based in Sipser's textbook. I find it very basic and quite useful for the introduction of the topic, but I would like to continue the ...
- 131
4
votes
2
answers
232
views
Efficiently finding an infix of a word that is rejected by an NFA
I am interested in the fine-grained complexity of the following NFA infix rejection problem:
Input: a word $w$, a nondeterministic finite automaton $A$
Output: is there an infix of $w$ (i.e., some $u$...
- 11.5k
12
votes
1
answer
827
views
Languages with infinite syntactic monoid
The notions of syntactic monoid and of the recognition of languages by monoids are usually introduced in the context of regular languages where one can prove that a language is regular iff it is ...
- 2,022
10
votes
1
answer
174
views
Resources on factorizations of regular languages
There is this paper [1] about the concept of universal automaton of a regular language, that makes heavy usage of the concept of factorization of a language $L$, i.e., a pair of maximal non-empty ...
- 2,022
8
votes
0
answers
104
views
A coalgebraic treatment for transfinite automata?
It is well known that (many different types of) automata can be modeled by coalgebras of one sort or another, and that their semantics can be defined by a map into a final coalgebra. This is roughly ...
- 1,001
9
votes
1
answer
710
views
Bounds on longest word rejected by a cofinite NFA
A cofinite NFA $A$ is an NFA recognizing a language $L(A)$ whose complement $\overline{L(A)}$ is finite. Consider the longest word $u$ in the complement $\overline{L(A)}$. How big can $|u|$ be, as a ...
- 11.5k
2
votes
0
answers
107
views
Hi, are there any books or long enough materials just for syntactic monoids?
Not just superficial information like how you would be able to find on wikipedia, nor just a single chapter on some automata theory textbook, I decided that I really want to dive deep into syntactic ...
0
votes
1
answer
186
views
Is there a recursive-enumerable list of Turing Machines which accept a recursive language each such that the list covers all recursive languages?
This is an excersize problem from Kozen:
Show that there exists an recursive-enumerable (r.e.) list of Turing machines such that every machine on the list accepts a recursive set and every recursive ...
11
votes
1
answer
230
views
Deciding if the languages of a set of DFAs forms a partition of $\Sigma^*$
Given an unambiguous automaton $\mathcal{A}$ ($\leq 1$ accepting run per word) over an alphabet $\Sigma$ , one can decide if it is universal (accepts all words) in polynomial time (proven here, ...
- 346