# Questions tagged [automata-theory]

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

336 questions
Filter by
Sorted by
Tagged with
511 views

### Decidability of membership in the fixed point of a rational relation

Given a finite alphabet $\Sigma$, a non-deterministic finite-state transducer representing rational a relation $T \subseteq \wp(\Sigma^* \times \Sigma^*)$, a finite state machine representing a ...
423 views

305 views

### Name this digraph

I am trying to track down the name of this digraph and some references: You take all members of the transformation semigroup on $n$ elements, $T_{n}$. For two members $x$ ,$y$ ; if $x$ is in the ...
Let $\xi$ be an infinite binary sequence, and denote by $T(\xi)$ the set of all factors (infixes) of $\xi$. Also if $w$ is some finite prefix of $\xi$, denote by $\xi/w$ the unique $\eta$ such that $w ... 1answer 234 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 ... 2answers 237 views ### Alternating automata In the paper Fast LTL to Buchi Automata Translation (2001, Gastin and Oddoux) the authors, while defining co-Buchi alternating automata define$\Sigma’= 2^\Sigma$where$\Sigma$is the alphabet. ... 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 2answers 224 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$\...
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?