Related Research Articles
In mathematics and computer science, the Krohn–Rhodes theory is an approach to the study of finite semigroups and automata that seeks to decompose them in terms of elementary components. These components correspond to finite aperiodic semigroups and finite simple groups that are combined in a feedback-free manner.
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. Deterministic refers to the uniqueness of the computation run. In search of the simplest models to capture finite-state machines, Warren McCulloch and Walter Pitts were among the first researchers to introduce a concept similar to finite automata in 1943.
In computer science, a linear bounded automaton is a restricted form of Turing machine.
In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input.
Umesh Virkumar Vazirani is an Indian-American academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in quantum computing. He is also a co-author of a textbook on algorithms.
Zvi Galil is an Israeli-American computer scientist and mathematician. Galil served as the President of Tel Aviv University from 2007 through 2009. From 2010 to 2019, he was the dean of the Georgia Institute of Technology College of Computing. His research interests include the design and analysis of algorithms, computational complexity and cryptography. He has been credited with coining the terms stringology and sparsification. He has published over 200 scientific papers and is listed as an ISI highly cited researcher.
Language equations are mathematical statements that resemble numerical equations, but the variables assume values of formal languages rather than numbers. Instead of arithmetic operations in numerical equations, the variables are joined by language operations. Among the most common operations on two languages A and B are the set union A ∪ B, the set intersection A ∩ B, and the concatenation A⋅B. Finally, as an operation taking a single operand, the set A* denotes the Kleene star of the language A. Therefore language equations can be used to represent formal grammars, since the languages generated by the grammar must be the solution of a system of language equations.
In computational complexity theory, the complexity class 2-EXPTIME (sometimes called 2-EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(22p(n)) time, where p(n) is a polynomial function of n.
DCFS, the International Workshop on Descriptional Complexity of Formal Systems is an annual academic conference in the field of computer science.
Michael Ezra Saks is an American mathematician. He is currently the Department Chair of the Mathematics Department at Rutgers University (2017–) and from 2006 until 2010 was director of the Mathematics Graduate Program at Rutgers University. Saks received his Ph.D. from the Massachusetts Institute of Technology in 1980 after completing his dissertation titled Duality Properties of Finite Set Systems under his advisor Daniel J. Kleitman.
In mathematics, the minimum k-cut, is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to at least k connected components. These edges are referred to as k-cut. The goal is to find the minimum-weight k-cut. This partitioning can have applications in VLSI design, data-mining, finite elements and communication in parallel computing.
Constantinos Daskalakis is a Greek theoretical computer scientist. He is a professor at MIT's Electrical Engineering and Computer Science department and a member of the MIT Computer Science and Artificial Intelligence Laboratory. He was awarded the Rolf Nevanlinna Prize and the Grace Murray Hopper Award in 2018.
Leslie Ann Goldberg is a professor of computer science at the University of Oxford and a Fellow of St Edmund Hall, Oxford. Her research concerns the design and analysis of algorithms for random sampling and approximate combinatorial enumeration.
In automata theory, a self-verifying finite automaton (SVFA) is a special kind of a nondeterministic finite automaton (NFA) with a symmetric kind of nondeterminism introduced by Hromkovič and Schnitger. Generally, in self-verifying nondeterminism, each computation path is concluded with any of the three possible answers: yes, no, and I do not know. For each input string, no two paths may give contradictory answers, namely both answers yes and no on the same input are not possible. At least one path must give answer yes or no, and if it is yes then the string is considered accepted. SVFA accept the same class of languages as deterministic finite automata (DFA) and NFA but have different state complexity.
State complexity is an area of theoretical computer science dealing with the size of abstract automata, such as different kinds of finite automata. The classical result in the area is that simulating an -state nondeterministic finite automaton by a deterministic finite automaton requires exactly states in the worst case.
Giovanni Pighizzini is an Italian theoretical computer scientist known for his work in formal language theory and particularly in state complexity of two-way finite automata. He earned his PhD in 1993 from the University of Milan, where he is a full professor since 2001. Pighizzini serves as the Steering Committee Chair of the annual Descriptional Complexity of Formal Systems academic conference since 2006.
Thomas Colcombet is a French theoretical computer scientist known for settling major open problems on tree walking automata jointly with Mikołaj Bojańczyk. Colcombet is currently a CNRS Research Director at Paris Diderot University.
Richard Emil Ladner is an American computer scientist known for his contributions to both theoretical computer science and assistive technology. Ladner is a professor emeritus at the University of Washington.
In economics, a budget-additive valuation is a kind of a utility function. It corresponds to a person that, when given a set of items, evaluates them in the following way:
References
- ↑ Geffert, Viliam (1993). "Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space". SIAM Journal on Computing. 22 (1): 102–113. doi:10.1137/0222009. ISSN 0097-5397.
- ↑ Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (1998). "Sublogarithmic Bounds on Space and Reversals". SIAM Journal on Computing. 28 (1): 325–340. doi:10.1137/S0097539796301306. hdl: 2434/178756 . ISSN 0097-5397. S2CID 37853723.
- ↑ Geffert, Viliam (2012). "An alternating hierarchy for finite automata". Theoretical Computer Science. 445: 1–24. doi: 10.1016/j.tcs.2012.04.044 . ISSN 0304-3975.
- ↑ Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2007). "Complementing two-way finite automata". Information and Computation. 205 (8): 1173–1187. doi: 10.1016/j.ic.2007.01.008 . ISSN 0890-5401.
- ↑ Franceschini, Gianni; Geffert, Viliam (2005). "An in-place sorting with O(nlog n) comparisons and O(n) moves". Journal of the ACM. 52 (4): 515–537. arXiv: cs/0305005 . doi:10.1145/1082036.1082037. ISSN 0004-5411. S2CID 2148080.
- ↑ Geffert, Viliam; Gajdoš, Jozef (2011). "In-Place Sorting". SOFSEM 2011: Theory and Practice of Computer Science. Lecture Notes in Computer Science. Vol. 6543. pp. 248–259. Bibcode:2011LNCS.6543..248G. doi:10.1007/978-3-642-18381-2_21. ISBN 978-3-642-18380-5. ISSN 0302-9743.
