The Experts below are selected from a list of 321 Experts worldwide ranked by ideXlab platform

Cyril Nicaud - One of the best experts on this subject based on the ideXlab platform.

  • Developments in Language Theory - Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata
    Developments in Language Theory, 2013
    Co-Authors: Sven De Felice, Cyril Nicaud
    Abstract:

    We study the number of states of the minimal Automaton of the mirror of a rational language recognized by a random Deterministic Automaton with n states. We prove that, for any d > 0, the probability that this number of states is greater than n d tends to 1 as n tends to infinity. As a consequence, the generic and average complexities of Brzozowski minimization algorithm are super-polynomial for the uniform distribution on Deterministic automata.

  • Brzozowski Algorithm Is Generically Super-Polynomial Deterministic Automata
    2013
    Co-Authors: Sven De Felice, Cyril Nicaud
    Abstract:

    We study the number of states of the minimal Automaton of the mirror of a rational language recognized by a random Deterministic Automaton with n states. We prove that, for any d > 0, the probability that this number of states is greater than nd tends to 1 as n tends to infinity. As a consequence, the generic and average complexities of Brzozowski minimization algorithm are super-polynomial for the uniform distribution on Deterministic automata.

  • distribution of the number of accessible states in a random Deterministic Automaton
    Symposium on Theoretical Aspects of Computer Science, 2012
    Co-Authors: Arnaud Carayol, Cyril Nicaud
    Abstract:

    We study the distribution of the number of accessible states in Deterministic and complete automata with n states over a k-letters alphabet. We show that as n tends to infinity and for a fixed alphabet size, the distribution converges in law toward a Gaussian centered around vkn and of standard deviation equivalent to k p n, for some explicit constants vk and k. Using this characterization, we give a simple algorithm for random uniform generation of accessible Deterministic and complete automata of size n of expected complexity O(n p n), which matches the best methods known so far. Moreover, if we allow a " variation around n in the size of the output Automaton, our algorithm is the first solution of linear expected complexity. Finally we show how this work can be used to study accessible automata (which are dicult to apprehend from a combinatorial point of view) through the prism of the simpler Deterministic and complete automata. As an example, we show how the average complexity inO(n log logn) for Moore’s minimization algorithm obtained by David for Deterministic and complete automata can be extended to accessible automata. 1998 ACM Subject Classification F.2 Analysis of algorithms and problem complexity

Tomáš Masopust - One of the best experts on this subject based on the ideXlab platform.

  • On Properties and State Complexity of Deterministic State-Partition Automata
    2012
    Co-Authors: Galina Jirásková, Tomáš Masopust
    Abstract:

    A Deterministic Automaton accepting a regular language L is a state-partition Automaton with respect to a projection P if the state set of the Deterministic Automaton accepting the projected language P(L), obtained by the standard subset construction, forms a partition of the state set of the Automaton. In this paper, we study fundamental properties of state-partition automata. We provide a construction of the minimal state-partition Automaton for a regular language and a projection, discuss closure properties of state-partition automata under the standard constructions of Deterministic automata for regular operations, and show that almost all of them fail to preserve the property of being a state-partition Automaton. Finally, we define the notion of a state-partition complexity, and prove the tight bound on the state-partition complexity of regular languages represented by incomplete Deterministic automata.

  • IFIP TCS - On properties and state complexity of Deterministic state-partition automata
    Lecture Notes in Computer Science, 2012
    Co-Authors: Galina Jirásková, Tomáš Masopust
    Abstract:

    A Deterministic Automaton accepting a regular language L is a state-partition Automaton with respect to a projection P if the state set of the Deterministic Automaton accepting the projected language P(L), obtained by the standard subset construction, forms a partition of the state set of the Automaton. In this paper, we study fundamental properties of state-partition automata. We provide a construction of the minimal state-partition Automaton for a regular language and a projection, discuss closure properties of state-partition automata under the standard constructions of Deterministic automata for regular operations, and show that almost all of them fail to preserve the property of being a state-partition Automaton. Finally, we define the notion of a state-partition complexity, and prove the tight bound on the state-partition complexity of regular languages represented by incomplete Deterministic automata.

Philippe Michiels - One of the best experts on this subject based on the ideXlab platform.

  • DBPL - Avoiding Unnecessary Ordering Operations in XPath
    Database Programming Languages, 2004
    Co-Authors: Jan Hidders, Philippe Michiels
    Abstract:

    We present a sound and complete rule set for determining whether sorting by document order and duplicate removal operations in the query plan of XPath expressions are unnecessary. Additionally we define a Deterministic Automaton that illustrates how these rules can be translated into an efficient algorithm. This work is an important first step in the understanding and tackling of XPath/XQuery optimization problems that are related to ordering and duplicate removal.

  • Avoiding unnecessary ordering operations in XPath
    Lecture Notes in Computer Science, 2004
    Co-Authors: Jan Hidders, Philippe Michiels
    Abstract:

    We present a sound and complete rule set for determining whether sorting by document order and duplicate removal operations in the query plan of XPath expressions are unnecessary. Additionally we define a Deterministic Automaton that illustrates how these rules can be translated into an efficient algorithm. This work is an important first step in the understanding and tackling of XPath/XQuery optimization problems that are related to ordering and duplicate removal.

Galina Jirásková - One of the best experts on this subject based on the ideXlab platform.

  • CSR - Cyclic Shift on Prefix-Free Languages
    Computer Science – Theory and Applications, 2013
    Co-Authors: Jozef Jirásek, Galina Jirásková
    Abstract:

    We prove that the cyclic shift of a prefix-free language represented by a minimal complete n-state Deterministic finite Automaton is recognized by a Deterministic Automaton of at most (2n − 3) n − 2 states. We also show that this bound is tight in the quaternary case, and that it cannot be met by using any smaller alphabet. In the ternary and binary cases, we still get exponential lower bounds.

  • On Properties and State Complexity of Deterministic State-Partition Automata
    2012
    Co-Authors: Galina Jirásková, Tomáš Masopust
    Abstract:

    A Deterministic Automaton accepting a regular language L is a state-partition Automaton with respect to a projection P if the state set of the Deterministic Automaton accepting the projected language P(L), obtained by the standard subset construction, forms a partition of the state set of the Automaton. In this paper, we study fundamental properties of state-partition automata. We provide a construction of the minimal state-partition Automaton for a regular language and a projection, discuss closure properties of state-partition automata under the standard constructions of Deterministic automata for regular operations, and show that almost all of them fail to preserve the property of being a state-partition Automaton. Finally, we define the notion of a state-partition complexity, and prove the tight bound on the state-partition complexity of regular languages represented by incomplete Deterministic automata.

  • IFIP TCS - On properties and state complexity of Deterministic state-partition automata
    Lecture Notes in Computer Science, 2012
    Co-Authors: Galina Jirásková, Tomáš Masopust
    Abstract:

    A Deterministic Automaton accepting a regular language L is a state-partition Automaton with respect to a projection P if the state set of the Deterministic Automaton accepting the projected language P(L), obtained by the standard subset construction, forms a partition of the state set of the Automaton. In this paper, we study fundamental properties of state-partition automata. We provide a construction of the minimal state-partition Automaton for a regular language and a projection, discuss closure properties of state-partition automata under the standard constructions of Deterministic automata for regular operations, and show that almost all of them fail to preserve the property of being a state-partition Automaton. Finally, we define the notion of a state-partition complexity, and prove the tight bound on the state-partition complexity of regular languages represented by incomplete Deterministic automata.

  • MFCS - Note on Minimal Finite Automata
    Mathematical Foundations of Computer Science 2001, 2001
    Co-Authors: Galina Jirásková
    Abstract:

    We show that for all n and α such that 1 ≤ n ≤ α ≤ 2n there is a minimal n-state nonDeterministic finite Automaton whose equivalent minimal Deterministic Automaton has exactly α states.

Daniel Kirsten - One of the best experts on this subject based on the ideXlab platform.

  • Distance desert automata and the star height problem
    RAIRO - Theoretical Informatics and Applications, 2005
    Co-Authors: Daniel Kirsten
    Abstract:

    We show that it is decidable in time complexity \(2^{2^{2^{O{(n)}}}}\) whether the language accepted by an n-state non-Deterministic Automaton is of star height one, which is the first ever complexity result for the star height one problem. To achieve this, we introduce distance desert automata as a joint generalization of distance automata and desert automata, and show the decidability of its limitedness problem by solving the underlying Burnside problem.

  • FoSSaCS - Distance Desert Automata and the Star Height One Problem
    Lecture Notes in Computer Science, 2004
    Co-Authors: Daniel Kirsten
    Abstract:

    We show that it is decidable in time complexity \(2^{2^{2^{O{(n)}}}}\) whether the language accepted by an n-state non-Deterministic Automaton is of star height one, which is the first ever complexity result for the star height one problem. To achieve this, we introduce distance desert automata as a joint generalization of distance automata and desert automata, and show the decidability of its limitedness problem by solving the underlying Burnside problem.