Zobrazeno 1 - 10
of 676
pro vyhledávání: '"Policriti A"'
Autor:
Becker, Ruben, Cenzato, Davide, Kim, Sung-Hwan, Kociumaka, Tomasz, Kodric, Bojana, Policriti, Alberto, Prezza, Nicola
Co-lex partial orders were recently introduced in (Cotumaccio et al., SODA 2021 and JACM 2023) as a powerful tool to index finite state automata, with applications to regular expression matching. They generalize Wheeler orders (Gagie et al., Theoreti
Externí odkaz:
http://arxiv.org/abs/2410.04771
Autor:
Becker, Ruben, Cenzato, Davide, Kim, Sung-Hwan, Kodric, Bojana, Policriti, Alberto, Prezza, Nicola
A Wheeler automaton is a finite state automaton whose states admit a total Wheeler order, reflecting the co-lexicographic order of the strings labeling source-to-node paths. A Wheeler language is a regular language admitting an accepting Wheeler auto
Externí odkaz:
http://arxiv.org/abs/2306.04737
In the present work, we lay out a new theory showing that all automata can always be co-lexicographically partially ordered, and an intrinsic measure of their complexity can be defined and effectively determined, namely, the minimum width $p$ of one
Externí odkaz:
http://arxiv.org/abs/2208.04931
Publikováno v:
In Theoretical Computer Science 24 October 2024 1013
Given an order of the underlying alphabet we can lift it to the states of a finite deterministic automaton: to compare states we use the order of the strings reaching them. When the order on strings is the co-lexicographic one \emph{and} this order t
Externí odkaz:
http://arxiv.org/abs/2203.12534
Publikováno v:
In Theoretical Computer Science 12 July 2024 1004
Publikováno v:
Algorithmica (2022) 1-26
Suffix trees are an important data structure at the core of optimal solutions to many fundamental string problems, such as exact pattern matching, longest common substring, matching statistics, and longest repeated substring. Recent lines of research
Externí odkaz:
http://arxiv.org/abs/2109.05290
The states of a deterministic finite automaton A can be identified with collections of words in Pf(L(A)) -- the set of prefixes of words belonging to the regular language accepted by A. But words can be ordered and among the many possible orders a ve
Externí odkaz:
http://arxiv.org/abs/2106.02309
Ordering the collection of states of a given automaton starting from an order of the underlying alphabet is a natural move towards a computational treatment of the language accepted by the automaton. Along this path, Wheeler \emph{graphs} have been r
Externí odkaz:
http://arxiv.org/abs/2106.00315
In the present work, we tackle the regular language indexing problem by first studying the hierarchy of $p$-sortable languages: regular languages accepted by automata of width $p$. We show that the hierarchy is strict and does not collapse, and provi
Externí odkaz:
http://arxiv.org/abs/2102.06798