@InProceedings{	  kl11lics,
  title		= "Languages of Dot-Depth One over Infinite Words",
  author	= "Manfred Kufleitner and Alexander Lauser",
  publisher	= "IEEE Computer Society",
  year		= "2011",
  bibdate	= "2011-08-10",
  bibsource	= "DBLP,
		  http://dblp.uni-trier.de/db/conf/lics/lics2011.html#KufleitnerL11",
  booktitle	= "IEEE Symposium on Logic in Computer Science (LICS) 2011,
		  Conference Proceedings",
  event_place	= "Toronto, ON, Canada",
  event_name	= "Logic in Computer Science (LICS), 2011 26th Annual IEEE
		  Symposium on",
  event_date	= "June 21--24, 2011",
  isbn		= "978-0-7695-4412-0",
  pages		= "23--32",
  url		= "http://dx.doi.org/10.1109/LICS.2011.24",
  abstract	= "Over finite words, languages of dot-depth one are
		  expressively complete for alternation-free first-order
		  logic. This fragment is also known as the Boolean closure
		  of existential first-order logic. Here, the atomic formulas
		  comprise order, successor, minimum, and maximum predicates.
		  Knast (1983) has shown that it is decidable whether a
		  language has dot-depth one. We extend Knast's result to
		  infinite words. In particular, we describe the class of
		  languages definable in alternation-free first-order logic
		  over infinite words, and we give an effective
		  characterization of this fragment. This characterization
		  has two components. The first component is identical to
		  Knast's algebraic property for finite words and the second
		  component is a topological property, namely being a Boolean
		  combination of Cantor sets. As an intermediate step we
		  consider finite and infinite words simultaneously. We then
		  obtain the results for infinite words as well as for finite
		  words as special cases. In particular, we give a new proof
		  of Knast's Theorem on languages of dot-depth one over
		  finite words.",
  doi		= "10.1109/LICS.2011.24"
}