The Experts below are selected from a list of 8685 Experts worldwide ranked by ideXlab platform
Beatrice Palano - One of the best experts on this subject based on the ideXlab platform.
-
iterated uniform finite state transducers descriptional complexity of Nondeterminism and two way motion
Descriptional Complexity of Formal Systems, 2020Co-Authors: Martin Kutrib, Carlo Mereghetti, Andreas Malcher, Beatrice PalanoAbstract:An iterated uniform finite-state transducer executes the same length-preserving transduction in iterative sweeps. The first sweep occurs on the input string, while any subsequent sweep works on the output of the previous one. We consider devices with one-way motion and two-way motion, i.e., sweeps are either from left to right only, or alternate from left to right and from right to left. In addition, devices may work deterministically or nondeterministically. Here, we restrict to study devices performing a constant number of sweeps, which are known to characterize exactly the regular languages. We determine the descriptional costs of removing two-way motion, Nondeterminism, and sweeps, and, in particular, the costs for the conversion to deterministic or nondeterministic finite automata. Finally, the special case of unary languages is investigated, and a language family is presented that is immune to the resources of Nondeterminism and two-way motion, in the sense that both resources can neither reduce the number of states nor the number of sweeps.
-
removing Nondeterminism in constant height pushdown automata
Information & Computation, 2014Co-Authors: Zuzana Bednarova, Viliam Geffert, Carlo Mereghetti, Beatrice PalanoAbstract:We study the descriptional cost of removing Nondeterminism in constant height pushdown automata-i.e., pushdown automata with a built-in constant limit on the height of the pushdown. We show a double-exponential size increase when converting a constant height nondeterministic pushdown automaton into an equivalent deterministic device. Moreover, we prove that such a double-exponential blow-up cannot be avoided by certifying its optimality. As a direct consequence, we get that eliminating Nondeterminism in classical finite state automata is single-exponential even with the help of a constant height pushdown store.
-
removing Nondeterminism in constant height pushdown automata
Descriptional Complexity of Formal Systems, 2012Co-Authors: Zuzana Bednarova, Viliam Geffert, Carlo Mereghetti, Beatrice PalanoAbstract:We study the descriptional cost of converting constant height nondeterministic pushdown automata into equivalent deterministic devices. We show a double-exponential upper bound for this conversion, together with a super-exponential lower bound.
Zuzana Bednarova - One of the best experts on this subject based on the ideXlab platform.
-
removing Nondeterminism in constant height pushdown automata
Information & Computation, 2014Co-Authors: Zuzana Bednarova, Viliam Geffert, Carlo Mereghetti, Beatrice PalanoAbstract:We study the descriptional cost of removing Nondeterminism in constant height pushdown automata-i.e., pushdown automata with a built-in constant limit on the height of the pushdown. We show a double-exponential size increase when converting a constant height nondeterministic pushdown automaton into an equivalent deterministic device. Moreover, we prove that such a double-exponential blow-up cannot be avoided by certifying its optimality. As a direct consequence, we get that eliminating Nondeterminism in classical finite state automata is single-exponential even with the help of a constant height pushdown store.
-
removing Nondeterminism in constant height pushdown automata
Descriptional Complexity of Formal Systems, 2012Co-Authors: Zuzana Bednarova, Viliam Geffert, Carlo Mereghetti, Beatrice PalanoAbstract:We study the descriptional cost of converting constant height nondeterministic pushdown automata into equivalent deterministic devices. We show a double-exponential upper bound for this conversion, together with a super-exponential lower bound.
Konstantinos Mamouras - One of the best experts on this subject based on the ideXlab platform.
-
synthesis of strategies using the hoare logic of angelic and demonic Nondeterminism
Logical Methods in Computer Science, 2017Co-Authors: Konstantinos MamourasAbstract:We study a propositional variant of Hoare logic that can be used for reasoning about programs that exhibit both angelic and demonic Nondeterminism. We work in an uninterpreted setting, where the meaning of the atomic actions is specified axiomatically using hypotheses of a certain form. Our logical formalism is entirely compositional and it subsumes the non-compositional formalism of safety games on finite graphs. We present sound and complete Hoare-style calculi that are useful for establishing partial-correctness assertions, as well as for synthesizing implementations. The computational complexity of the Hoare theory of dual Nondeterminism is investigated using operational models, and it is shown that the theory is complete for exponential time.
-
synthesis of strategies and the hoare logic of angelic Nondeterminism
Foundations of Software Science and Computation Structure, 2015Co-Authors: Konstantinos MamourasAbstract:We study a propositional variant of Hoare logic that can be used for reasoning about programs that exhibit both angelic and demonic Nondeterminism. We work in an uninterpreted setting, where the meaning of the atomic actions is specified axiomatically using hypotheses of a certain form. Our logical formalism is entirely compositional and it subsumes the non-compositional formalism of safety games on finite graphs. We present sound and complete Hoare-style (partial-correctness) calculi that are useful for establishing Hoare assertions, as well as for synthesizing implementations. The computational complexity of the Hoare theory of dual Nondeterminism is investigated using operational models, and it is shown that the theory is complete for exponential time.
Larissa Werlein - One of the best experts on this subject based on the ideXlab platform.
-
regulated Nondeterminism in pushdown automata
Theoretical Computer Science, 2009Co-Authors: Martin Kutrib, Andreas Malcher, Larissa WerleinAbstract:A generalization of pushdown automata towards regulated Nondeterminism is studied. The Nondeterminism is governed in such a way that the decision, whether or not a nondeterministic rule is applied, depends on the whole content of the stack. More precisely, the content of the stack is considered as a word over the stack alphabet, and the pushdown automaton is allowed to act nondeterministically, if this word belongs to some given set R of control words. Otherwise its behavior is deterministic. It turns out that non-context-free languages can be accepted if R is a context-free and non-regular language. On the other hand, if the control sets R are regular languages, then the resulting devices are not more powerful than nondeterministic pushdown automata. This raises the natural question of the relations between the structure and complexity of regular sets R on one hand and the computational capacity of the corresponding R-PDA on the other hand. The main result of the paper shows that an infinite proper hierarchy of regular control sets leads to an infinite proper hierarchy of the corresponding language classes. Additionally, closure properties and decision problems of these language classes are investigated.
-
regulated Nondeterminism in pushdown automata
International Conference on Implementation and application of automata, 2007Co-Authors: Martin Kutrib, Andreas Malcher, Larissa WerleinAbstract:A generalization of pushdown automata towards regulated Nondeterminism is studied. The Nondeterminism is governed in such a way that the decision, whether or not a nondeterministic rule is applied, depends on the whole content of the stack. More precisely, the content of the stack is considered as a word over the stack alphabet, and the pushdown automaton is allowed to act nondeterministically, if this word belongs to some given set R of control words. Otherwise its behavior is deterministic. The computational capacity of such R-PDAs depends on the complexity of R. It turns out that non-context-free languages are accepted even if R is a linear, deterministic context-free language. On the other hand, regular control sets R do not increase the computational capacity of nondeterministic pushdown automata. This raises the natural question for the relations between the structure and complexity of regular sets R on one hand and the computational capacity of the corresponding R-PDA on the other hand. Clearly, if R is empty, the deterministic context-free languages are characterized. For R = {a, b}* one obtains all context-free languages. Furthermore, if R is finite, then the regular closure of the deterministic context-free languages is described. We investigate these questions, and discuss closure properties of the language classes in question under AFL operations.
Iyad A Kanj - One of the best experts on this subject based on the ideXlab platform.
-
using Nondeterminism to design efficient deterministic algorithms
Algorithmica, 2004Co-Authors: Jianer Chen, Donald K Firesen, Weijia Jia, Iyad A KanjAbstract:In this paper we illustrate how Nondeterminism can be used conveniently and effectively in designing efficient deterministic algorithms. In particular, our method gives a parameterized algorithm of running time O((5.7 k)k n) for the 3-D matching problem, which significantly improves the previous algorithm by Downey et al. The algorithm can be generalized to yield an improved algorithm for the r-D matching problem for any positive integer r. The method can also be employed in designing deterministic algorithms for other optimization problems as well.
-
using Nondeterminism to design efficient deterministic algorithms
Lecture Notes in Computer Science, 2001Co-Authors: Jianer Chen, Weijia Jia, Donald K Friesen, Iyad A KanjAbstract:In this paper, we illustrate how Nondeterminism can be used conveniently and effectively in designing efficient deterministic algorithms. In particular, our method gives an O((5.7k) k n) parameterized algorithm for the 3-D matching problem, which significantly improves the previous algorithm by Downey, Fellows, and Koblitz. The algorithm can be generalized to yield an improved algorithm for the r-D matching problem for any positive integer r. The method can also be employed in designing deterministic algorithms for other optimization problems as well.
