Se dice que un lenguaje regular está libre de estrellas si se puede describir mediante una expresión regular construida a partir de las letras del alfabeto , el símbolo del conjunto vacío , todos los operadores booleanos , incluida la complementación , y la concatenación, pero no la estrella de Kleene . [1] Por ejemplo, el idioma de las palabras sobre el alfabeto que no tienen a consecutivas se pueden definir por , dónde denota el complemento de un subconjunto de . La condición es equivalente a tener una altura de estrella generalizada cero.
Un ejemplo de un idioma regular que no está libre de estrellas es . [2]
Marcel-Paul Schützenberger caracterizó los lenguajes sin estrellas como aquellos con monoides sintácticos aperiódicos . [3] [4] También se pueden caracterizar lógicamente como lenguajes definibles en FO [<], la lógica de primer orden sobre los números naturales con la relación menor que, [5] como lenguajes libres de contador [6] y como lenguajes definibles en lógica temporal lineal . [7]
Todos los idiomas sin estrellas están en uniforme AC 0 .
Ver también
Referencias
- ^ Lawson (2004) p.235
- ^ Arto Salomaa (1981). Joyas de la teoría del lenguaje formal . Prensa de Ciencias de la Computación. pag. 53. ISBN 978-0-914894-69-8.
- ^ Marcel-Paul Schützenberger (1965). "Sobre monoides finitos que tienen sólo subgrupos triviales" (PDF) . Información y Computación . 8 (2): 190-194. doi : 10.1016 / s0019-9958 (65) 90108-7 .
- ^ Lawson (2004) p.262
- ^ Straubing, Howard (1994). Autómatas finitos, lógica formal y complejidad de circuitos . Progreso en Informática Teórica. Basilea: Birkhäuser. pag. 79 . ISBN 3-7643-3719-2. Zbl 0816.68086 .
- ^ McNaughton, Robert; Papert, Seymour (1971). Autómatas sin contador . Monografía de investigación. 65 . Con un apéndice de William Henneman. Prensa del MIT. ISBN 0-262-13076-9. Zbl 0232.94024 .
- ^ Kamp, Johan Antony Willem (1968). La lógica tensa y la teoría del orden lineal . Universidad de California en Los Ángeles (UCLA).
- Lawson, Mark V. (2004). Autómatas finitos . Chapman y Hall / CRC. ISBN 1-58488-255-7. Zbl 1086.68074 .
- Diekert, Volker; Gastin, Paul (2008). "Lenguajes definibles de primer orden". En Jörg Flum; Erich Grädel; Thomas Wilke (eds.). Lógica y autómatas: historia y perspectivas (PDF) . Prensa de la Universidad de Amsterdam. ISBN 978-90-5356-576-6.