Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Mediating for reduction (on minimizing alternating Buchi automata)
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
2014 (Engelska)Ingår i: Theoretical Computer Science, ISSN 0304-3975, Vol. 552, 26-43 s.Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We propose a new approach for minimizing alternating Buchi automata (ABA). The approach is based on the mediated equivalence on states of an ABA, which is the maximal equivalence contained in the mediated preorder. Two states p and q are related by the mediated preorder if there is a mediator (mediating state) which forward simulates p and backward simulates q. Under further conditions, letting a computation on some word jump from q to p preserves the language as the automaton can anyway already accept the word without jumps by runs through the mediator. We further show how the mediated equivalence can be computed efficiently. Finally, we show that, compared to the standard forward simulation equivalence, the mediated equivalence can yield much larger reductions when applied within the process of complementing Buchi automata where ABA are used as an intermediate model.

Ort, förlag, år, upplaga, sidor
2014. Vol. 552, 26-43 s.
Nyckelord [en]
Alternating Buchi automata, Simulation, Reduction, Quotient
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:uu:diva-235302DOI: 10.1016/j.tcs.2014.08.003ISI: 000342475400003OAI: oai:DiVA.org:uu-235302DiVA: diva2:761502
Tillgänglig från: 2014-11-06 Skapad: 2014-10-30 Senast uppdaterad: 2014-11-06Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas

Övriga länkar

Förlagets fulltext

Sök vidare i DiVA

Av författaren/redaktören
Abdulla, Parosh Aziz
Av organisationen
Datorteknik
I samma tidskrift
Theoretical Computer Science
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

Altmetricpoäng

Totalt: 449 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf