|
Self-verifying Finite Automaton
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 Juraj Hromkovič, 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. Formal definition An SVFA is represented formally by a n-tuple, 6-tuple, ''A''=(''Q'', Σ, Δ, ''q0'', ''Fa'', ''Fr'') such that (''Q'', Σ, Δ, ''q0'', ''Fa'') is an ''nondeterministic finite automaton, NFA'', and ''Fa'', ''Fr'' a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Automata Theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton (automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite-State Machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states (represented in the figure by circles) and transitions (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its transition function, which takes the previous state and current input symbol as its arguments. Automata theo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nondeterministic Finite Automaton
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if * each of its transitions is ''uniquely'' determined by its source state and input symbol, and * reading an input symbol is required for each state transition. A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is ''not'' a DFA, but not in this article. Using the subset construction algorithm, each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same formal language. Like DFAs, NFAs only recognize regular languages. NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott, who also showed their equivalence to DFAs. NFAs are used in the implementation of regular expressions: Thompson's construction is an algorithm for compiling a regular expression to an NFA that ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Juraj Hromkovič
Juraj Hromkovič (born 1958) is a Slovak Computer Scientist and Professor at ETH Zürich. He is the author of numerous monographs and scientific publications in the field of algorithmics, computational complexity theory, and randomization. Biography Hromkovič was born 1958 in Bratislava. He studied at Comenius University where he received his Ph.D. in 1986 ( Dr. rer. nat.), habilitated in 1989 (''Theoretical Cybernetics and Mathematical Informatics''), and worked as a lecturer from 1989 to 1990. From 1989 to 1994, he was a visiting professor at the group of ''Burkhard Monien'' at the University of Paderborn. In 1994, he received a professorship at the ''Institute of Informatics'' at the University of Kiel. From 1997 to 2003, he led the ''Chair of Computer Science 1'' at RWTH Aachen. Since 2004, he has been a professor at the Federal Institute of Technology, Zurich for Information Technology and Education. Next to active research in various fields of theoretical computer scien ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Deterministic Finite Automata
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. Hopcroft 2001: ''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. The figure illustrates a deterministic finite automaton using a state diagram. In this example automaton, there are three states: S0, S1, and S2 (denoted graphically by circles). The automaton takes a finite sequence of 0s and 1s as input. For each state, there is a transition arrow leading out to a next state f ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 n-state nondeterministic finite automaton by a deterministic finite automaton requires exactly 2^n states in the worst case. Transformation between variants of finite automata Finite automata can be deterministic and nondeterministic, one-way (DFA, NFA) and two-way (2DFA, 2NFA). Other related classes are unambiguous (UFA), self-verifying (SVFA) and alternating (AFA) finite automata. These automata can also be two-way (2UFA, 2SVFA, 2AFA). All these machines can accept exactly the regular languages. However, the size of different types of automata necessary to accept the same language (measured in the number of their states) may be different. For any two types of finite automata, the ''state complexity tradeoff'' between them is an integer function f where f(n) is the least numb ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
N-tuple
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defined inductively using the construction of an ordered pair. Mathematicians usually write tuples by listing the elements within parentheses "" and separated by a comma and a space; for example, denotes a 5-tuple. Sometimes other symbols are used to surround the elements, such as square brackets "nbsp; or angle brackets "⟨ ⟩". Braces "" are used to specify arrays in some programming languages but not in mathematical expressions, as they are the standard notation for sets. The term ''tuple'' can often occur when discussing other mathematical objects, such as vectors. In computer science, tuples come in many forms. Most typed functional programming languages implement tuples directly as product types, tightly associated with algebr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Giovanni Pighizzini
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. Research contributions Pighizzini obtained optimal state complexity tradeoffs between different types of finite automata over a one-letter alphabet, In particular, in his joint paper with Geffert and Mereghetti he presented the first simulation of two-way nondeterministic finite automata by two-way deterministic finite automata using Savitch's theorem, contributing to the 2DFA vs. 2NFA open question. Jointly with Jirásková, he determined state complexity of self-verifying finite automata. He also contributed to the computational complexity theory In theoretical co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
