Separation for ωB- and ωS-regular Languages

Date Issued
01-01-2016
Author(s)
Hutchison, David
Kanade, Takeo
Kittler, Josef
Kleinberg, Jon M.
Mattern, Friedemann
Mitchell, John C.
Naor, Moni
Indian Institute of Technology, Madras
Steffen, Bernhard
Terzopoulos, Demetri
Tygar, Doug
Weikum, Gerhard
Skrzypczak, Michał
DOI
Abstract
In this chapter we study the classes of ωB- and ωS-regular languages, introduced by Bojańczyk and Colcombet in [BC06]. These languages of ?-words are defined as those that can be recognised by a certain model of counter automata with asymptotic acceptance condition. Both these classes are strictly contained in the class of mso+u-definable languages, the advantage of these classes is that they admit effective constructions.
Volume
9802 LNCS