Back to Search
Start Over
An Improved Construction of Deterministic Omega-automaton Using Derivatives
- Source :
- Fundamenta Informaticae. 119:393-406
- Publication Year :
- 2012
- Publisher :
- IOS Press, 2012.
-
Abstract
- In an earlier paper, the author used derivatives to construct a deterministic automaton recognizing the language defined by an ω-regular expression. The construction was related to a determinization method invented by Safra. This paper describes a new construction, inspired by Piterman's improvement to Safra's method. It produces an automaton with fewer states. In addition, the presentation and proofs are simplified by going via a nondeterministic automaton having derivatives as states.
- Subjects :
- Discrete mathematics
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Algebra and Number Theory
Theoretical computer science
Powerset construction
Timed automaton
Pushdown automaton
Büchi automaton
Nonlinear Sciences::Cellular Automata and Lattice Gases
Theoretical Computer Science
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Computational Theory and Mathematics
Deterministic automaton
Computer Science::Logic in Computer Science
Probabilistic automaton
Two-way deterministic finite automaton
Nondeterministic finite automaton
Computer Science::Formal Languages and Automata Theory
Information Systems
Mathematics
Subjects
Details
- ISSN :
- 01692968
- Volume :
- 119
- Database :
- OpenAIRE
- Journal :
- Fundamenta Informaticae
- Accession number :
- edsair.doi...........f7da735d090ccb04f0cd22b938460835