Zobrazeno 1 - 10
of 144
pro vyhledávání: '"McKenzie, Pierre"'
Autor:
Li, Yaqiao, McKenzie, Pierre
A model of computation for which reasonable yet still incomplete lower bounds are known is the read-once branching program. Here variants of complexity measures successful in the study of read-once branching programs are defined and studied. Some new
Externí odkaz:
http://arxiv.org/abs/2305.11276
Autor:
Li, Yaqiao, McKenzie, Pierre
Publikováno v:
In Information and Computation December 2024 301 Part A
Publikováno v:
Logical Methods in Computer Science, Volume 18, Issue 3 (August 2, 2022) lmcs:7110
The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class $\mathsf{NC^1}$. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condit
Externí odkaz:
http://arxiv.org/abs/2101.07495
Publikováno v:
Logical Methods in Computer Science, Volume 13, Issue 3 (September 13, 2017) lmcs:3928
The well-quasi-ordering (i.e., a well-founded quasi-ordering such that all antichains are finite) that defines well-structured transition systems (WSTS) is shown not to be the weakest hypothesis that implies decidability of the coverability problem.
Externí odkaz:
http://arxiv.org/abs/1608.02636
A formulation of "Ne\v{c}iporuk's lower bound method" slightly more inclusive than the usual complexity-measure-specific formulation is presented. Using this general formulation, limitations to lower bounds achievable by the method are obtained for s
Externí odkaz:
http://arxiv.org/abs/1608.01932
Autor:
Elias, Yara, McKenzie, Pierre
Publikováno v:
INTEGERS, Volume 14, A16, 2014, http://www.integers-ejcnt.org/vol14.html
Given integers d >= 1, and g >= 2, a g-addition chain for d is a sequence of integers a_0=1, a_1, a_2,..., a_{r-1}, a_r=d where a_i=a_{j_1}+a_{j_2}+...+a_{j_k}, with 2 =< k =< g, and 0 =< j_1 =< j_2 =< ... =< j_k =< i-1. The length of a g-addition ch
Externí odkaz:
http://arxiv.org/abs/1607.07011
Determining the complexity of the reachability problem for vector addition systems with states (VASS) is a long-standing open problem in computer science. Long known to be decidable, the problem to this day lacks any complexity upper bound whatsoever
Externí odkaz:
http://arxiv.org/abs/1412.4259
Publikováno v:
EPTCS 63, 2011, pp. 93-102
The Parikh finite word automaton model (PA) was introduced and studied by Klaedtke and Ruess in 2003. Here, by means of related models, it is shown that the bounded languages recognized by PA are the same as those recognized by deterministic PA. More
Externí odkaz:
http://arxiv.org/abs/1108.3625
The Parikh finite word automaton (PA) was introduced and studied by Klaedtke and Ruess in 2003. Natural variants of the PA arise from viewing a PA equivalently as an automaton that keeps a count of its transitions and semilinearly constrains their nu
Externí odkaz:
http://arxiv.org/abs/1101.1547
We introduce the Tree Evaluation Problem, show that it is in logDCFL (and hence in P), and study its branching program complexity in the hope of eventually proving a superlogarithmic space lower bound. The input to the problem is a rooted, balanced d
Externí odkaz:
http://arxiv.org/abs/1005.2642