<oai_dc:dc xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd">
  <dc:creator>Allred, Joel</dc:creator>
  <dc:creator>Ultes-Nitsche, Ulrich</dc:creator>
  <dc:date>2015-03-01</dc:date>
  <dc:description xmlns:ns0="xml" ns0:lang="en">Complementation of Büchi automata is well known for being difficult. In the worst case, a state-space growth of (0:76n)n is unavoidable. Recent studies suggest that “simpler” algorithms perform better than more involved ones on practical cases. In this paper, we present a simple “direct” algorithm for complementing Büchi automata. It involves a structured subset construction (using tuples of subsets of states) that produces a deterministic automaton. This construction leads to a complementation procedure that resembles the straightforward complementation algorithm for deterministic Büchi automata, the latter algorithm actually being a special case of our construction.</dc:description>
  <dc:format>application/pdf</dc:format>
  <dc:identifier>https://folia.unifr.ch/global/documents/304914</dc:identifier>
  <dc:identifier>https://folia.unifr.ch/documents/304914/files/IWP15_01_diuf.pdf</dc:identifier>
  <dc:language>eng</dc:language>
  <dc:rights>info:eu-repo/semantics/openAccess</dc:rights>
  <dc:rights>License undefined</dc:rights>
  <dc:subject>info:eu-repo/classification/udc/004</dc:subject>
  <dc:title xmlns:ns1="xml" ns1:lang="en">Complementing Büchi automata with a subset-tuple construction</dc:title>
  <dc:type>http://purl.org/coar/resource_type/c_18ws</dc:type>
</oai_dc:dc>