Self-verifying finite automata and descriptional complexity
From MaRDI portal
Publication:2829967
Recommendations
- Optimal simulation of self-verifying automata by deterministic automata
- Converting Self-verifying Automata into Deterministic Automata
- Operations on Self-Verifying Finite Automata
- Computational complexity of decision problems on self-verifying finite automata
- scientific article; zbMATH DE number 7444008
Cites work
- scientific article; zbMATH DE number 5595151 (Why is no real title available?)
- scientific article; zbMATH DE number 3254905 (Why is no real title available?)
- scientific article; zbMATH DE number 3353192 (Why is no real title available?)
- A lower bound technique for the size of nondeterministic finite automata
- An upper bound for transforming self-verifying automata into deterministic ones
- Kleene star on unary regular languages
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Nondeterminism and the size of two way finite automata
- On cliques in graphs
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Operations on Self-Verifying Finite Automata
- Optimal simulation of self-verifying automata by deterministic automata
- Partial orders on words, minimal elements of regular languages, and state complexity
- Quotient complexity of regular languages
- Reversal of binary regular languages
- State complexity of some operations on binary regular languages
- Succinct representation of regular languages by Boolean automata
- The state complexities of some basic operations on regular languages
Cited in
(14)- scientific article; zbMATH DE number 1810490 (Why is no real title available?)
- SELF-SPECIFYING MACHINES
- Self-verifying pushdown and queue automata
- An upper bound for transforming self-verifying automata into deterministic ones
- Computational complexity of decision problems on self-verifying finite automata
- Converting Self-verifying Automata into Deterministic Automata
- Self-verifying Cellular Automata
- Optimal simulation of self-verifying automata by deterministic automata
- scientific article; zbMATH DE number 7444008 (Why is no real title available?)
- Descriptional and computational complexity of finite automata -- a survey
- Operations on Self-Verifying Finite Automata
- Self-verifying cellular automata
- scientific article; zbMATH DE number 2086408 (Why is no real title available?)
- Affine automata verifiers
This page was built for publication: Self-verifying finite automata and descriptional complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2829967)
