The Experts below are selected from a list of 20394 Experts worldwide ranked by ideXlab platform
N. Klarlund - One of the best experts on this subject based on the ideXlab platform.
-
Determinizing Asynchronous Automata on Infinite Inputs
BRICS Report Series, 1995Co-Authors: N. Klarlund, Madhavan Mukund, Milind SohoniAbstract:Asynchronous automata are a natural distributed machine model for recognizing trace languages - languages defined over an alphabet equipped with an independence relation. To handle infinite traces, Gastin and Petit introduced Buchi asynchronous automata, which accept precisely the class of omega-regular trace languages. Like their sequential counterparts, these automata need to be non-deterministic in order to capture all omega-regular languages. Thus complementation of these automata is non-trivial. Complementation is an important operation because it is fundamental for treating the logical connective "not" in decision procedures for monadic second-order logics. Subsequently, Diekert and Muscholl solved the complementation problem by showing that with a Muller acceptance condition, deterministic automata suffice for recognizing omega-regular trace languages. However, a direct determinization procedure, extending the classical Subset Construction, has proved elusive. In this paper, we present a direct determinization procedure for Buchi asynchronous automata, which generalizes Safra's Construction for sequential Buchi automata. As in the sequential case, the blow-up in the state space is essentially that of the underlying Subset Construction.
-
Proving nondeterministically specified safety properties using progress measures
Information and Computation, 1993Co-Authors: N. Klarlund, Fred B. SchneiderAbstract:Abstract Using the notion of progress measures, we discuss verification methods for proving that a program satisfies a property specified by an automaton having finite nondeterminism. Such automata can express any safety property. Previous methods, which can be derived from the method presented here, either rely on transforming the program or are not complete. In contrast, our ND progress measures describe a homomorphism from the unaltered program to a canonical specification automaton and constitute a complete verification method. The canonical specification automaton is obtained from the classical Subset Construction and a new Subset Construction, called historization.
-
Progress measures, immediate determinacy, and a Subset Construction for tree automata
DAIMI Report Series, 1992Co-Authors: N. KlarlundAbstract:Using the concept of progress measure, we give a new proof of Rabin's fundamental result that the languages defined by tree automata are closed under complementation. To do this we show that for certain infinite games based on tree automata, an immediate determinacy property holds for the player who is trying to win according to a Rabin acceptance condition. Immediate determinacy is stronger than the forgetful determinacy of Gurevich and Harrington, which depends on more information about the past, but applies to another class of games. Next, we show a graph theoretic duality theorem for winning conditions. Finally, we present an extended version of Safra's determinization Construction. Together, these ingredients and the determinacy of Borel games yield a straightforward recipe for complementing tree automata. Our Construction is almost optimal, i.e. the state space blow-up is essentially exponential --- thus roughly the same as for automata on finite or infinite words. To our knowledge, no prior Constructions have been better than double exponential.
-
Progress measures, immediate determinacy, and a Subset Construction for tree automata
[1992] Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science, 1992Co-Authors: N. KlarlundAbstract:Using the concept of a progress measure, a simplified proof is given of M.O. Rabin's (1969) fundamental result that the languages defined by tree automata are closed under complementation. To do this, it is shown that for infinite games based on tree automata, the forgetful determinacy property of Y. Gurevich and L. Harrington (1982) can be strengthened to an immediate determinacy property for the player who is trying to win according to a Rabin acceptance condition. Moreover, a graph-theoretic duality theorem for such acceptance conditions is shown. Also presented is a strengthened version of S. Safra's (1988) determinization Construction. Together these results and the determinacy of Borel games yield a straightforward method for complementing tree automata.
-
LICS - Progress measures, immediate determinacy, and a Subset Construction for tree automata
[1992] Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science, 1Co-Authors: N. KlarlundAbstract:Using the concept of a progress measure, a simplified proof is given of M.O. Rabin's (1969) fundamental result that the languages defined by tree automata are closed under complementation. To do this, it is shown that for infinite games based on tree automata, the forgetful determinacy property of Y. Gurevich and L. Harrington (1982) can be strengthened to an immediate determinacy property for the player who is trying to win according to a Rabin acceptance condition. Moreover, a graph-theoretic duality theorem for such acceptance conditions is shown. Also presented is a strengthened version of S. Safra's (1988) determinization Construction. Together these results and the determinacy of Borel games yield a straightforward method for complementing tree automata. >
Alain Terlutte - One of the best experts on this subject based on the ideXlab platform.
-
residual finite state automata
Symposium on Theoretical Aspects of Computer Science, 2002Co-Authors: Francois Denis, Aurelien Lemay, Alain TerlutteAbstract:We define a new variety of Nondeterministic Finite Automata (NFA): a Residual Finite State Automaton (RFSA) is an NFA all the states of which define residual languages of the language L that it recognizes; a residual language according to a word u is the set of words v such that uv is in L. We prove that every regular language is recognized by a unique (canonical) RFSA which has a minimal number of states and a maximal number of transitions. Canonical RFSAs are based on the notion of prime residual languages, i.e. that are not the union of other residual languages. We provide an algorithmic Construction of the canonical RFSA similar to the Subset Construction used to build the minimal DFA from a given NFA. We study the size of canonical RFSAs and the complexity of our Constructions.
-
STACS - Residual Finite State Automata
2002Co-Authors: Francois Denis, Aurelien Lemay, Alain TerlutteAbstract:We define a new variety of Nondeterministic Finite Automata (NFA): a Residual Finite State Automaton (RFSA) is an NFA all the states of which define residual languages of the language L that it recognizes; a residual language according to a word u is the set of words v such that uv is in L. We prove that every regular language is recognized by a unique (canonical) RFSA which has a minimal number of states and a maximal number of transitions. Canonical RFSAs are based on the notion of prime residual languages, i.e. that are not the union of other residual languages. We provide an algorithmic Construction of the canonical RFSA similar to the Subset Construction used to build the minimal DFA from a given NFA. We study the size of canonical RFSAs and the complexity of our Constructions.
Moshe Y. Vardi - One of the best experts on this subject based on the ideXlab platform.
-
STACS - The Büchi complementation saga
STACS 2007, 2007Co-Authors: Moshe Y. VardiAbstract:The complementation problem for nondeterministic word automata has numerous applications in formal verification. In particular, the language-containment problem, to which many verification problems are reduced, involves complementation. For automata on finite words, which correspond to safety properties, complementation involves determinization. The 2n blow-up that is caused by the Subset Construction is justified by a tight lower bound. For Buchi automata on infinite words, which are required for the modeling of liveness properties, optimal complementation Constructions are quite complicated, as the Subset Construction is not sufficient. We review here progress on this problem, which dates back to its introduction in Buchi's seminal 1962 paper.
-
the buchi complementation saga
Symposium on Theoretical Aspects of Computer Science, 2007Co-Authors: Moshe Y. VardiAbstract:The complementation problem for nondeterministic word automata has numerous applications in formal verification. In particular, the language-containment problem, to which many verification problems are reduced, involves complementation. For automata on finite words, which correspond to safety properties, complementation involves determinization. The 2n blow-up that is caused by the Subset Construction is justified by a tight lower bound. For Buchi automata on infinite words, which are required for the modeling of liveness properties, optimal complementation Constructions are quite complicated, as the Subset Construction is not sufficient. We review here progress on this problem, which dates back to its introduction in Buchi's seminal 1962 paper.
-
buchi complementation made tighter
Automated Technology for Verification and Analysis, 2006Co-Authors: Ehud Friedgu, Orna Kupferma, Moshe Y. VardiAbstract:The complementation problem for nondeterministic word automata has numerous applications in formal verification. In particular, the language-containment problem, to which many verification problems is reduced, involves complementation. For automata on finite words, which correspond to safety properties, complementation involves determinization. The 2 n blow-up that is caused by the Subset Construction is justified by a tight lower bound. For Buchi automata on infinite words, which are required for the modeling of liveness properties, optimal complementation Constructions are quite complicated, as the Subset Construction is not sufficient. From a theoretical point of view, the problem is considered solved since 1988, when Safra came up with a determinization Construction for Buchi automata, leading to a 2 O(nlog n) complementation Construction, and Michel came up with a matching lower bound. A careful analysis, however, of the exact blow-up in Safra’s and Michel’s bounds reveals an exponential gap in the constants hiding in the O() notations: while the upper bound on the number of states in Safra’s complementary automaton is n 2n, Michel’s lower bound involves only an n! blow up, which is roughly (n/e) n . The exponential gap exists also in more recent complementation Constructions. In particular, the upper bound on the number of states in the complementation Construction in [KV01], which avoids determinization, is (6n) n . This is in contrast with the case of automata on finite words, where the upper and lower bounds coincides. In this work we describe an improved complementation Construction for nondeterministic Buchi automata and analyze its complexity. We show that the new Construction results in an automaton with at most (1.06n) n states. While this leaves the problem about the exact blow up open, the gap is now exponentially smaller. From a practical point of view, our solution enjoys the simplicity of [KV01], and results in much smaller automata.
-
LPAR - Experimental evaluation of classical automata Constructions
Logic for Programming Artificial Intelligence and Reasoning, 2005Co-Authors: Deian Tabakov, Moshe Y. VardiAbstract:There are several algorithms for producing the canonical DFA from a given NFA. While the theoretical complexities of these algorithms are known, there has not been a systematic empirical comparison between them. In this work we propose a probabilistic framework for testing the performance of automata-theoretic algorithms. We conduct a direct experimental comparison between Hopcroft’s and Brzozowski’s algorithms. We show that while Hopcroft’s algorithm has better overall performance, Brzozowski’s algorithm performs better for “high-density” NFA. We also consider the universality problem, which is traditionally solved explicitly via the Subset Construction. We propose an encoding that allows this problem to be solved symbolically via a model-checker. We compare the performance of this approach to that of the standard explicit algorithm, and show that the explicit approach performs significantly better.
-
ATVA - BÜCHI COMPLEMENTATION MADE TIGHTER
Automated Technology for Verification and Analysis, 2004Co-Authors: Ehud Friedgut, Orna Kupferman, Moshe Y. VardiAbstract:The complementation problem for nondeterministic word automata has numerous applications in formal verification. In particular, the language-containment problem, to which many verification problems is reduced, involves complementation. For automata on finite words, which correspond to safety properties, complementation involves determinization. The 2 n blow-up that is caused by the Subset Construction is justified by a tight lower bound. For Buchi automata on infinite words, which are required for the modeling of liveness properties, optimal complementation Constructions are quite complicated, as the Subset Construction is not sufficient. From a theoretical point of view, the problem is considered solved since 1988, when Safra came up with a determinization Construction for Buchi automata, leading to a 2 O(nlog n) complementation Construction, and Michel came up with a matching lower bound. A careful analysis, however, of the exact blow-up in Safra’s and Michel’s bounds reveals an exponential gap in the constants hiding in the O() notations: while the upper bound on the number of states in Safra’s complementary automaton is n 2n, Michel’s lower bound involves only an n! blow up, which is roughly (n/e) n . The exponential gap exists also in more recent complementation Constructions. In particular, the upper bound on the number of states in the complementation Construction in [KV01], which avoids determinization, is (6n) n . This is in contrast with the case of automata on finite words, where the upper and lower bounds coincides. In this work we describe an improved complementation Construction for nondeterministic Buchi automata and analyze its complexity. We show that the new Construction results in an automaton with at most (1.06n) n states. While this leaves the problem about the exact blow up open, the gap is now exponentially smaller. From a practical point of view, our solution enjoys the simplicity of [KV01], and results in much smaller automata.
J.-m. Champarnaud - One of the best experts on this subject based on the ideXlab platform.
-
Random generation models for NFA'S
2004Co-Authors: J.-m. Champarnaud, Georges Hansel, Thomas Paranthoën, Djelloul ZiadiAbstract:The aim of this study is the random generation of non-deterministic automata. We focus our attention on the random generation processed with bitstreams for which we present a probabilistic analysis. Let m be the size of the alphabet. We show that the DFAs obtained by Subset Construction from n-state NFAs based on equiprobable bitstreams have a probability of being of size m + 2 that tends to 1 when n tends to infinity. This property gives an asymptotical explanation to van Zijl's experimental results concerning the succinctness of NFAs. We also determine the probability that a state is reachable from an equiprobably chosen DFA state. We show that the distribution of the Subsets that appear during the Subset Construction is an equiprobable one in the case of bitstreams generated with the probability 2 - 2n-1/n. This result is related to the conjecture of Leslie, Raymond and Wood, which says that the number of states of the DFA is maximum when the density of the NFA is approximately equal to 2/n. Finally we extend this probabilistic study to the case of *-NFAs defined by van Zijl.
-
Compact and fast algorithms for safe regular expression search
International Journal of Computer Mathematics, 2004Co-Authors: J.-m. Champarnaud, Fabien Coulon, Thomas ParanthoënAbstract:This article describes an improvement of the brute force determinization algorithm in the case of homogeneous nondeterministic finite automata (NFAs), as well as its application to pattern matching. Brute force determinization with limited memory may provide a partially determinized automaton, but its bounded complexity makes it a safe procedure contrary to the classical Subset Construction. Actually, our algorithm is inspired by both recent results of Champarnaud concerning the Subset automaton of a homogeneous NFA and the algorithm recently designed by Navarro and Raffinot to implement the brute force determinization of the Glushkov NFA of a regular pattern. Our algorithm significantly improves Navarro–Raffinot's one since it has an average exponentially smaller memory requirement for a given level of determinization, which, considering a bounded memory, implies a quadratically smaller parsing time. This algorithm has been implemented in CCP software (http://www.univ-rouen.fr/LIFAR/aia/ccp.html). Tests ...
-
Subset Construction complexity for homogeneous automata, position automata and ZPC-structures
Theoretical Computer Science, 2001Co-Authors: J.-m. ChamparnaudAbstract:The aim of this paper is to investigate how Subset Construction performs on specific families of automata. A new upper bound on the number of states of the Subset-automaton is established in the case of homogeneous automata. The complexity of the two basic steps of Subset Construction, i.e. the computation of deterministic transitions and the set equality tests, is examined depending on whether the nondeterministic automaton is an unrestricted one, an homogeneous one, a position one or a ZPC-structure, which is an implicit Construction for a position automaton. Copyright 2001 Elsevier Science B.V.
-
Subset Construction complexity for homogeneous automata, position automata and ZPC-structures
Theoretical Computer Science, 2001Co-Authors: J.-m. ChamparnaudAbstract:AbstractThe aim of this paper is to investigate how Subset Construction performs on specific families of automata. A new upper bound on the number of states of the Subset-automaton is established in the case of homogeneous automata. The complexity of the two basic steps of Subset Construction, i.e. the computation of deterministic transitions and the set equality tests, is examined depending on whether the nondeterministic automaton is an unrestricted one, an homogeneous one, a position one or a ZPC-structure, which is an implicit Construction for a position automaton
-
Workshop on Implementing Automata - Determinization of Glushkov Automata
Lecture Notes in Computer Science, 1999Co-Authors: J.-m. Champarnaud, Djelloul Ziadi, Jean-luc PontyAbstract:We establish a new upper bound on the number of states of the automaton yielded by the determinization of a Glushkov automaton. We show that the ZPC structure, which is an implicit Construction for Glushkov automata, leads to an efficient implementation of the Subset Construction.
Francois Denis - One of the best experts on this subject based on the ideXlab platform.
-
residual finite state automata
Symposium on Theoretical Aspects of Computer Science, 2002Co-Authors: Francois Denis, Aurelien Lemay, Alain TerlutteAbstract:We define a new variety of Nondeterministic Finite Automata (NFA): a Residual Finite State Automaton (RFSA) is an NFA all the states of which define residual languages of the language L that it recognizes; a residual language according to a word u is the set of words v such that uv is in L. We prove that every regular language is recognized by a unique (canonical) RFSA which has a minimal number of states and a maximal number of transitions. Canonical RFSAs are based on the notion of prime residual languages, i.e. that are not the union of other residual languages. We provide an algorithmic Construction of the canonical RFSA similar to the Subset Construction used to build the minimal DFA from a given NFA. We study the size of canonical RFSAs and the complexity of our Constructions.
-
STACS - Residual Finite State Automata
2002Co-Authors: Francois Denis, Aurelien Lemay, Alain TerlutteAbstract:We define a new variety of Nondeterministic Finite Automata (NFA): a Residual Finite State Automaton (RFSA) is an NFA all the states of which define residual languages of the language L that it recognizes; a residual language according to a word u is the set of words v such that uv is in L. We prove that every regular language is recognized by a unique (canonical) RFSA which has a minimal number of states and a maximal number of transitions. Canonical RFSAs are based on the notion of prime residual languages, i.e. that are not the union of other residual languages. We provide an algorithmic Construction of the canonical RFSA similar to the Subset Construction used to build the minimal DFA from a given NFA. We study the size of canonical RFSAs and the complexity of our Constructions.
