Function defined on formal languages in computer science
Brzozowski derivative (on red background) of a dictionary string set with respect to the string "con"
In theoretical computer science, in particular in formal language theory, the Brzozowski derivative of a set of strings and a string is the set of all strings obtainable from a string in by cutting off the prefix . Formally:
.
For example,
The Brzozowski derivative was introduced under various different names since the late 1950s.[1][2][3]
Today it is named after the computer scientist Janusz Brzozowski who investigated its properties and gave an algorithm to compute the derivative of a generalized regular expression.[4]
^George N. Raney (Apr 1958). "Sequential functions". Journal of the ACM. 5 (2): 177–180. doi:10.1145/320924.320930. S2CID 1611992.
^Dana Scott and Michael Rabin (Apr 1959). "Finite Automata and Their Decision Problems" (PDF). IBM Journal of Research and Development. 3 (2): 114–125. doi:10.1147/rd.32.0114.
^C.C. Elgot and J.D. Rutledge (Oct 1961). "Operations on finite automata". In Robert S. Ledley (ed.). Proc. AIEE 2nd Ann. Symp. on Switching, Circuit Theory, and Logical Design (SWCT), Detroit. pp. 129–132. doi:10.1109/FOCS.1961.26.
^Janusz A. Brzozowski (1964). "Derivatives of Regular Expressions". J ACM. 11 (4): 481–494. doi:10.1145/321239.321249. S2CID 14126942.
and 14 Related for: Brzozowski derivative information
computer science, in particular in formal language theory, the Brzozowskiderivative u−1S{\displaystyle u^{-1}S} of a set S{\displaystyle S} of strings...
Brzozowska Brzozów County (Polish: powiat brzozowski), a territory in south-eastern Poland Brzozowskiderivative Олег Иосифович Губарь, "101 вопрос об Одессе"...
program Brzozowskiderivative – Function defined on formal languages in computer science Dini derivative – Class of generalisations of the derivative Fractal...
These closure properties hold for both left and right quotients. Brzozowskiderivative Linz, Peter (2011). An Introduction to Formal Languages and Automata...
complexity to O(n2). For a set S of strings and a string u, the Brzozowskiderivative u−1S is defined as the set of all rest-strings obtainable from a...
singleton language L1 and an arbitrary language L2 is known as Brzozowskiderivative; if L2 is represented by a regular expression, so can be the left...
Jelliffe, Rick (10 March 2010). "What is a Packrat Parser? What are BrzozowskiDerivatives?". Archived from the original on 28 July 2011. For example, there...
cell discovery. Janusz Brzozowski, Polish-Canadian computer scientist known for developing the Brzozowskiderivative and Brzozowski's algorithm. Aleksander...
bridge in the world. Janusz Brzozowski: computer scientist known for developing the Brzozowskiderivative and Brzozowski's algorithm. Tytus Liwiusz Burattini:...
Dmowskiego, London 1984. Zionism and the Polish cause (in Polish) Stanisław Brzozowski Aleksandr Dugin Ibn Khaldun Oswald Spengler Jan Stachniuk Arnold J. Toynbee...
attunement, and permadeath for mercenary characters. 2018 KeeperRL Michal Brzozowski Fantasy WIN, LIN, MAC "a turn based dungeon building game that can be...
for a black-box problem Hopcroft's algorithm, Moore's algorithm, and Brzozowski's algorithm: algorithms for minimizing the number of states in a deterministic...
Global Information
