en>Nbarth: /* Transcendental functions */ condition number formula

2013-04-22T14:48:14Z

Transcendental functions: condition number formula

New page

In [[automata theory]], a '''permutation automaton''', or '''pure-group automaton''', is a [[deterministic finite automaton]] such that each input symbol [[permutation|permutes]] the set of states.<ref name=McNaughton1967>{{Citation
| title = The loop complexity of pure-group events
|date=August 1967
| author = McNaughton, Robert
| journal = Information and Control
| pages = 167–176
| volume = 11
| issue = 1-2
| doi=10.1016/S0019-9958(67)90481-0
}}</ref><ref>{{cite journal |last=Thierrin|first=Gabriel|date=March 1968|title=Permutation automata|journal=Theory of Computing Systems|volume=2|issue=1|pages=83–90|doi=10.1007/BF01691347}}</ref>

Formally, a deterministic finite automaton {{mvar|A}} may be defined by the tuple (''Q'', Σ, δ, ''q''''0'', ''F''),
where ''Q'' is the set of states of the automaton, Σ is the set of input symbols, δ is the [[transition function]] that takes a state ''q'' and an input symbol ''x'' to a new state δ(''q'',''x''), ''q''''0'' is the initial state of the automaton, and ''F'' is the set of accepting states (also: final states) of the automaton. {{mvar|A}} is a permutation automaton if and only if, for every two distinct states {{math|''qi''}} and {{math|''qj''}} in ''Q'' and every input symbol {{mvar|x}} in Σ, δ(''qi'',''x'') ≠ δ(''qj'',''x'').

A [[formal language]] is '''p-regular''' (also: a '''pure-group language''') if it is accepted by a permutation automaton. For example, the set of strings of even length forms a p-regular language: it may be accepted by a permutation automaton with two states in which every transition replaces one state by the other.

== Applications ==
The pure-group languages were the first interesting family of [[regular languages]] for which the [[star height problem]] was proved to be [[computable]].<ref name=McNaughton1967 /><ref name="Brzozowski80">[[Janusz Brzozowski (computer scientist)|Janusz A. Brzozowski]]: ''Open problems about regular languages'', In: Ronald V. Book, editor, ''Formal language theory—Perspectives and open problems'', pp. 23–47. Academic Press, 1980 [https://www.cs.uwaterloo.ca/research/tr/1980/CS-80-03.pdf (technical report version)]</ref>

Another mathematical problem on regular languages is the ''separating words problem'', which asks for the size of a smallest deterministic finite automaton that distinguishes between two given words of length at most ''n'' – by accepting one word and rejecting the other. The known upper bound in the general case is <math>O(n^{2/5}(\log n)^{3/5})</math>.<ref>{{cite doi|10.1007/978-3-642-22600-7_12}}</ref> The problem was later studied for the restriction to permutation automata. In this case, the known upper bound changes to <math>O(n^{1/2})</math>.<ref>{{Citation
| author = J. M. Robson
| title = Separating words with machines and groups
| url = http://www.numdam.org/item?id=ITA_1996__30_1_81_0
| year = 1996
| journal = RAIRO – Informatique théorique et applications
| pages = 81–86
| volume = 30
| issue = 1
| accessdate = 2012-07-15
}}</ref>

== References ==
{{reflist}}

[[Category:Automata theory]]
[[Category:Formal languages]]
[[Category:Permutations]]

{{formalmethods-stub}}

Significance arithmetic - Revision history

en>Nbarth: /* Transcendental functions */ condition number formula