Self-verifying finite automata and descriptional complexity
From MaRDI portal
Publication:2829967
DOI10.1007/978-3-319-41114-9_3zbMATH Open1476.68131OpenAlexW2482365960MaRDI QIDQ2829967FDOQ2829967
Authors: Galina Jirásková 
Publication date: 9 November 2016
Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01633958/file/416473_1_En_3_Chapter.pdf
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
- The state complexities of some basic operations on regular languages
- On cliques in graphs
- Title not available (Why is that?)
- A lower bound technique for the size of nondeterministic finite automata
- Title not available (Why is that?)
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- State complexity of some operations on binary regular languages
- Reversal of binary regular languages
- Title not available (Why is that?)
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Nondeterminism and the size of two way finite automata
- Partial orders on words, minimal elements of regular languages, and state complexity
- Succinct representation of regular languages by Boolean automata
- Quotient complexity of regular languages
- Optimal simulation of self-verifying automata by deterministic automata
- An upper bound for transforming self-verifying automata into deterministic ones
- Kleene star on unary regular languages
- Operations on Self-Verifying Finite Automata
Cited In (14)
- Title not available (Why is that?)
- SELF-SPECIFYING MACHINES
- Self-verifying pushdown and queue automata
- An upper bound for transforming self-verifying automata into deterministic ones
- Converting Self-verifying Automata into Deterministic Automata
- Computational complexity of decision problems on self-verifying finite automata
- Self-verifying Cellular Automata
- Optimal simulation of self-verifying automata by deterministic automata
- Title not available (Why is that?)
- Descriptional and computational complexity of finite automata -- a survey
- Operations on Self-Verifying Finite Automata
- Self-verifying cellular automata
- Title not available (Why is that?)
- 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)
