1 October 2004 in Information and Computation
1 January 2004 in RAIRO - Theoretical Informatics and Applications
This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence of several other formal systems, including a certain restricted class of Turing machines and a certain type of language equations, thus giving further evidence for the importance of the language family they all generate.
1 August 2013 in Computer Science Review
13 December 2007 in RAIRO - Theoretical Informatics and Applications
The cyclic shift of a language L, defined as SHIFT(L) = {vu | uv ∈ L}, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov's pioneering paper on the state complexity of regular language operations [Soviet Math. Dokl. 11 (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! . 2(n-1)(n-2), which shows that the state complexity of cyclic shift is 2 n2+ nlogn - O(n) for alphabets with at least 4 letters. For 2- and 3-letter alphabets, we prove state complexity. We also establish a tight 2n2+1 lower bound for the nondeterministic state complexity of this operation using a binary alphabet.
21 August 2008 in Theory of Computing Systems
28 May 2009 in Theoretical Computer Science