SAT-based Minimization of Deterministic -Automata

Authors

Souheib Baarir, Alexandre Duret-Lutz

Where

Proceedings of the 20th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR'15)

Type

inproceedings

Publisher

Springer

Projects

Spot

Date

2015-09-01

Abstract

We describe a tool that inputs a deterministic ω-automaton with any acceptance condition, and synthesizes an equivalent ω-automaton with another arbitrary acceptance condition and a given number of states, if such an automaton exists. This tool, that relies on a SAT-based encoding of the problem, can be used to provide minimal ω-automata equivalent to given properties, for different acceptance conditions.

Documents

• Paper

Bibtex (lrde.bib)

@InProceedings{	  baarir.15.lpar,
  author	= {Souheib Baarir and Alexandre Duret-Lutz},
  booktitle	= {Proceedings of the 20th International Conference on Logic
		  for Programming, Artificial Intelligence, and Reasoning
		  (LPAR'15)},
  title		= {{SAT}-based Minimization of Deterministic
		  $\omega$-Automata},
  year		= {2015},
  month		= nov,
  pages		= {79--87},
  publisher	= {Springer},
  volume	= {9450},
  series	= {Lecture Notes in Computer Science},
  abstract	= {We describe a tool that inputs a deterministic
		  $\omega$-automaton with any acceptance condition, and
		  synthesizes an equivalent $\omega$-automaton with another
		  arbitrary acceptance condition and a given number of
		  states, if such an automaton exists. This tool, that relies
		  on a SAT-based encoding of the problem, can be used to
		  provide minimal $\omega$-automata equivalent to given
		  properties, for different acceptance conditions.}
}