Permutační automat - Permutation automaton

v teorie automatů, a permutační automatnebo automat čisté skupiny, je deterministický konečný automat tak, že každý vstupní symbol permutuje množina států.^[1]^[2]

Formálně deterministický konečný automat $A$ mohou být definovány n-ticí (Q, Σ, δ, q₀, F),kde Q je sada stavů automatu, Σ je sada vstupních symbolů, δ je přechodová funkce to trvá stát q a vstupní symbol X do nového stavu δ (q,X), q₀ je počáteční stav automatu a F je sada přijímajících stavů (také: konečných stavů) automatu. $A$ je permutační automat tehdy a jen tehdy, pro každé dva odlišné stavy $q i$ a $q j$ v Q a každý vstupní symbol $X$ v Σ, δ (q_i,X) ≠ δ (q_j,X).

A formální jazyk je p-pravidelný (také: a jazyk čisté skupiny) pokud je to akceptováno permutačním automatem. Například sada řetězců sudé délky tvoří p-regulární jazyk: může ji přijmout permutační automat se dvěma stavy, ve kterých každý přechod nahradí jeden stav druhým.

Aplikace

Jazyky čisté skupiny byly první zajímavou rodinou běžné jazyky pro které problém s výškou hvězdy bylo prokázáno, že je vypočitatelný.^[1]^[3]

Dalším matematickým problémem běžných jazyků je problém s oddělováním slov, který požaduje velikost nejmenšího deterministického konečného automatu, který rozlišuje maximálně dvě daná slova délky n - přijetím jednoho slova a odmítnutím druhého. Známá horní hranice v obecném případě je ${ displaystyle O (n ^ {2/5} ( log n) ^ {3/5})}$ .^[4] Problém byl později studován u omezení na permutační automaty. V tomto případě se známá horní hranice změní na ${ displaystyle O (n ^ {1/2})}$ .^[5]

Reference

^ ^A ^b McNaughton, Robert (srpen 1967), „Smyčková složitost událostí čisté skupiny“, Informace a kontrola, 11 (1–2): 167–176, doi:10.1016 / S0019-9958 (67) 90481-0
^ Thierrin, Gabriel (březen 1968). "Permutační automaty". Teorie výpočetních systémů. 2 (1): 83–90. doi:10.1007 / BF01691347.
^ Janusz A. Brzozowski: Otevřené problémy s běžnými jazyky, In: Ronald V. Book, editor, Teorie formálního jazyka - Perspektivy a otevřené problémy, s. 23–47. Academic Press, 1980 (verze technické zprávy)
^ Demaine, E. D.; Eisenstat, S .; Shallit, J.; Wilson, D. A. (2011). "Poznámky k oddělování slov". Popisná složitost formálních systémů. Přednášky z informatiky. 6808. 147–157. doi:10.1007/978-3-642-22600-7_12. ISBN 978-3-642-22599-4.
^ J. M. Robson (1996), "Oddělování slov pomocí strojů a skupin", RAIRO - Informační technologie a aplikace, 30 (1): 81–86, vyvoláno 2012-07-15

Tento formální metody související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[McNaughton1967-1] A ^b McNaughton, Robert (srpen 1967), „Smyčková složitost událostí čisté skupiny“, Informace a kontrola, 11 (1–2): 167–176, doi:10.1016 / S0019-9958 (67) 90481-0

[2] Thierrin, Gabriel (březen 1968). "Permutační automaty". Teorie výpočetních systémů. 2 (1): 83–90. doi:10.1007 / BF01691347.

[Brzozowski80-3] Janusz A. Brzozowski: Otevřené problémy s běžnými jazyky, In: Ronald V. Book, editor, Teorie formálního jazyka - Perspektivy a otevřené problémy, s. 23–47. Academic Press, 1980 (verze technické zprávy)

[4] Demaine, E. D.; Eisenstat, S .; Shallit, J.; Wilson, D. A. (2011). "Poznámky k oddělování slov". Popisná složitost formálních systémů. Přednášky z informatiky. 6808. 147–157. doi:10.1007/978-3-642-22600-7_12. ISBN 978-3-642-22599-4.

[5] J. M. Robson (1996), "Oddělování slov pomocí strojů a skupin", RAIRO - Informační technologie a aplikace, 30 (1): 81–86, vyvoláno 2012-07-15

[1]

[2]

[3]

[4]

[5]