Some applications of a technique of Sakoda and Sipser
- 1 November 1990
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 21 (4) , 73-77
- https://doi.org/10.1145/101371.101375
Abstract
Sakoda and Sipser [Sa78] introduced a technique for constructing certain regular languages over a large alphabet and used these languages as candidates for proving lower bounds on the size increase when converting a nondeterministic finite automaton (NFA) to a deterministic one (DFA). The purpose of this note is to show that their method is quite useful in solving several problems in the theory of regular languages. In view of its intuitive appeal, we recommend it as a pedagogic aid for presenting lower bound proofs.Keywords
This publication has 6 references indexed in Scilit:
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their RepresentationSIAM Journal on Computing, 1989
- Lower bounds on the size of sweeping automataPublished by Association for Computing Machinery (ACM) ,1979
- Nondeterminism and the size of two way finite automataPublished by Association for Computing Machinery (ACM) ,1978
- A note on multiple-entry finite automataJournal of Computer and System Sciences, 1976
- Economy of description by automata, grammars, and formal systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1971
- On the Recognition of Primes by AutomataJournal of the ACM, 1968