loading...
Bounds in w-Regularity
Seattle, Washington August 12-August 15
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2006.1721st Annual IEEE Symposium on Logic i ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Mikolaj Bojanczyk, Thomas Colcombet, "Bounds in w-Regularity," Logic in Computer Science, Symposium on, pp. 285-296, 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/LICS.2006.17,
author = {Mikolaj Bojanczyk and Thomas Colcombet},
title = {Bounds in w-Regularity},
journal ={Logic in Computer Science, Symposium on},
volume = {0},
year = {2006},
issn = {1043-6871},
pages = {285-296},
doi = {http://doi.ieeecomputersociety.org/10.1109/LICS.2006.17},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Logic in Computer Science, Symposium on
TI - Bounds in w-Regularity
SN - 1043-6871
SP285
EP296
A1 - Mikolaj Bojanczyk,
A1 - Thomas Colcombet,
PY - 2006
KW - null
VL - 0
JA - Logic in Computer Science, Symposium on
ER -
 
Mikolaj Bojanczyk, LIAFA, France
Thomas Colcombet, CNRS/IRISA, France
We consider an extension of w-regular expressions where two new variants of the Kleene star L* are added: LB and L^S. These exponents act as the standard star, but restrict the number of iterations to be bounded (for LB) or to tend toward infinity (for L^S). These expressions can define languages that are not w-regular.

We develop a theory for these languages. We study the decidability and closure questions. We also define an equivalent automaton model, extending Buchi automata. This culminates with a -- partial -- complementation result.

Citation:
Mikolaj Bojanczyk, Thomas Colcombet, "Bounds in w-Regularity," lics, pp.285-296, 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.