Jazyk bez hvězd - Star-free language
A běžný jazyk se říká, že je bez hvězd pokud to lze popsat a regulární výraz zkonstruována z písmen abeceda, prázdná sada symbol, vše logické operátory - počítaje v to doplňování - a zřetězení ale ne Kleene hvězda.[1] Například jazyk slov nad abecedou které nemají za sebou následující a mohou být definovány , kde označuje doplněk podmnožiny z . Podmínka je ekvivalentní s zobecněná výška hvězdy nula.
Příkladem běžného jazyka, který není bez hvězd, je .[2]
Marcel-Paul Schützenberger charakterizované jazyky bez hvězd jako ty s neperiodické syntaktické monoidy.[3][4] Lze je také logicky charakterizovat jako jazyky definovatelné v FO [<], logika prvního řádu nad přirozenými čísly s relací méně než,[5] jako bezplatné jazyky[6] a jako jazyky definovatelné v lineární časová logika.[7]
Všechny jazyky bez hvězd jsou v uniformě AC0.
Viz také
Reference
- ^ Lawson (2004), s. 235
- ^ Arto Salomaa (1981). Klenoty teorie formálního jazyka. Computer Science Press. p. 53. ISBN 978-0-914894-69-8.
- ^ Marcel-Paul Schützenberger (1965). „Na konečných monoidech majících pouze triviální podskupiny“ (PDF). Informace a výpočet. 8 (2): 190–194. doi:10.1016 / s0019-9958 (65) 90108-7.
- ^ Lawson (2004), s. 262
- ^ Straubing, Howard (1994). Konečné automaty, formální logika a složitost obvodů. Pokrok v teoretické informatice. Basilej: Birkhäuser. p.79. ISBN 3-7643-3719-2. Zbl 0816.68086.
- ^ McNaughton, Robert; Papert, Seymour (1971). Bezplatné automaty. Výzkumná monografie. 65. S dodatkem od Williama Hennemana. MIT Stiskněte. ISBN 0-262-13076-9. Zbl 0232.94024.
- ^ Kamp, Johan Antony Willem (1968). Napjatá logika a teorie lineárního řádu. Kalifornská univerzita v Los Angeles (UCLA).
- Lawson, Mark V. (2004). Konečné automaty. Chapman and Hall / CRC. ISBN 1-58488-255-7. Zbl 1086.68074.
- Diekert, Volker; Gastin, Paul (2008). "Definovatelné jazyky prvního řádu". V Jörg Flum; Erich Grädel; Thomas Wilke (eds.). Logika a automaty: historie a perspektivy (PDF). Amsterdam University Press. ISBN 978-90-5356-576-6.
P ≟ NP | Tento teoretická informatika –Vztahující se článek je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |