CIAA2003

START ConferenceManager

Succinct Descriptions of Regular Languages with Binary Symmetric Difference NFAs

L. van Zijl

Presented at Eighth International Conference on Implementation and Application of Automata (CIAA 2003), July 16-18, 2003 Santa Barbara, CA, USA

Abstract

Champarnaud analyzed the number of states obtained from a binary symmetric difference NFA during the subset construction. We extend this work to an experimental analysis of the size of the minimal DFAs obtained from binary symmetric difference NFAs. We then consider the number of distinct languages accepted by binary symmetric difference NFAs, and compare that to Domaratzki's results for (traditional) binary NFAs.