The Experts below are selected from a list of 288 Experts worldwide ranked by ideXlab platform
Juha Honkala - One of the best experts on this subject based on the ideXlab platform.
-
The sequence Equivalence Problem for primitive D0L systems
Journal of Computer and System Sciences, 2013Co-Authors: Juha HonkalaAbstract:The D0L sequence Equivalence Problem consists of deciding, given two morphisms g:X^@?->X^@?, h:X^@?->X^@? and a word w@?X^@?, whether or not g^i(w)=h^i(w) for all i>=0. We show that in case of primitive morphisms, to decide the D0L sequence Equivalence Problem, it suffices to consider the terms of the sequences with i
-
The Sequence Equivalence Problem for Marked DT0L Systems
Fundamenta Informaticae, 2011Co-Authors: Juha HonkalaAbstract:We study the DT0L sequence Equivalence Problem for marked morphisms. We show that to decide this Problem it is enough to consider initial terms involving at most 2n morphisms where n is the cardinality of the underlying alphabet.
-
A new bound for the D0L sequence Equivalence Problem
Acta Informatica, 2006Co-Authors: Juha HonkalaAbstract:The D0L sequence Equivalence Problem consists of deciding, given two morphisms $$g:X^{\ast}\longrightarrow X^{\ast}$$, $$h:X^{\ast}\longrightarrow X^{\ast}$$ and a word $$w\in X^{\ast}$$, whether or not g i (w) = hi(w) for all i ≥ 0. We show that in case of smooth and loop-free morphisms, to decide the D0L sequence Equivalence Problem, it suffices to consider the terms of the sequences with $$i < 7n^3\sqrt{n\log n}$$, where n is the cardinality of X.
-
The Equivalence Problem for languages defined by transductions on D0L languages
International Journal of Computer Mathematics, 2005Co-Authors: Juha HonkalaAbstract:We study the Equivalence Problem for languages defined by various types of transducers acting on D0L languages. We show that, given ϵ-free sequential transducers S 1, …, S k , T 1, …, T k and D0L languages L 1, L 2, whether or not |S 1|(L 1)∪···∪|S k |(L 1)=|T 1|(L 2)∪···∪|T k |(L 2) is decidable.
-
An n 2-bound for the ultimate Equivalence Problem of certain D0L systems over an n-letter alphabet
Journal of Computer and System Sciences, 2005Co-Authors: Juha HonkalaAbstract:The ultimate Equivalence Problem for D0L systems consists of deciding, given two morphisms g:X^*@?X^*, h:X^*@?X^* and a word [email protected]?X^*, whether or not g^i(w)=h^i(w) for all but finitely many i>=0. We show that for a large class of D0L systems, to decide the ultimate Equivalence Problem, it suffices to check whether or not g^i(w)=h^i(w) holds for suitably chosen card(X)^2 consecutive values of i.
Vladimir A Zakharov - One of the best experts on this subject based on the ideXlab platform.
-
on the Equivalence Problem for programs with mode switching
International Conference on Implementation and application of automata, 2005Co-Authors: R I Podlovchenko, Dmitry Rusakov, Vladimir A ZakharovAbstract:We study a formal model of imperative sequential programs and focus on the Equivalence Problem for some class of programs with mode switching whose runs can be divided into two stages. In the first stage a program selects an appropriate mode of computation. Several modes may be tried (switched) in turn before making the ultimate choice. Every time when the next mode is put to a test, the program brings data to some predefined state. In the second stage of the run, once a definite mode is fixed, the final result of computation is produced. We develop a new technique for simulating the behavior of such programs by means of finite automata and demonstrate that the Equivalence Problem for programs with mode switching is decidable within a polynomial space. By revealing a close relationships between the Equivalence Problem for this class of programs and the intersection emptiness Problem for deterministic finite automata we show that the the former is PSPACE-complete.
-
the Equivalence Problem for computational models decidable and undecidable cases
Machines Computations and Universality, 2001Co-Authors: Vladimir A ZakharovAbstract:This paper presents a survey of fundamental concepts and main results in studying the Equivalence Problem for computer programs. We introduce some of the most-used models of computer programs, give a brief overview of the attempts to refine the boarder between decidable and undecidable cases of the Equivalence Problem for these models, and discuss the techniques for proving the decidability of the Equivalence Problem.
-
MCU - The Equivalence Problem for Computational Models: Decidable and Undecidable Cases
Lecture Notes in Computer Science, 2001Co-Authors: Vladimir A ZakharovAbstract:This paper presents a survey of fundamental concepts and main results in studying the Equivalence Problem for computer programs. We introduce some of the most-used models of computer programs, give a brief overview of the attempts to refine the boarder between decidable and undecidable cases of the Equivalence Problem for these models, and discuss the techniques for proving the decidability of the Equivalence Problem.
James Worrell - One of the best experts on this subject based on the ideXlab platform.
-
revisiting the Equivalence Problem for finite multitape automata
arXiv: Formal Languages and Automata Theory, 2013Co-Authors: James WorrellAbstract:The decidability of determining Equivalence of deterministic multitape automata (or transducers) was a longstanding open Problem until it was resolved by Harju and Karhum\"{a}ki in the early 1990s. Their proof of decidability yields a co_NP upper bound, but apparently not much more is known about the complexity of the Problem. In this paper we give an alternative proof of decidability, which follows the basic strategy of Harju and Karhumaki but replaces their use of group theory with results on matrix algebras. From our proof we obtain a simple randomised algorithm for deciding language Equivalence of deterministic multitape automata and, more generally, multiplicity Equivalence of nondeterministic multitape automata. The algorithm involves only matrix exponentiation and runs in polynomial time for each fixed number of tapes. If the two input automata are inequivalent then the algorithm outputs a word on which they differ.
-
on the complexity of the Equivalence Problem for probabilistic automata
Foundations of Software Science and Computation Structure, 2012Co-Authors: Stefan Kiefer, Andrzej S. Murawski, Joël Ouaknine, Björn Wachter, James WorrellAbstract:Deciding Equivalence of probabilistic automata is a key Problem for establishing various behavioural and anonymity properties of probabilistic systems. In recent experiments a randomised Equivalence test based on polynomial identity testing outperformed deterministic algorithms. In this paper we show that polynomial identity testing yields efficient algorithms for various generalisations of the Equivalence Problem. First, we provide a randomized NC procedure that also outputs a counterexample trace in case of inEquivalence. Second, we consider Equivalence of probabilistic cost automata. In these automata transitions are labelled with integer costs and each word is associated with a distribution on costs, corresponding to the cumulative costs of the accepting runs on that word. Two automata are equivalent if they induce the same cost distributions on each input word. We show that Equivalence can be checked in randomised polynomial time. Finally we show that the Equivalence Problem for probabilistic visibly pushdown automata is logspace equivalent to the Problem of whether a polynomial represented by an arithmetic circuit is identically zero.
-
FoSSaCS - On the complexity of the Equivalence Problem for probabilistic automata
Foundations of Software Science and Computational Structures, 2012Co-Authors: Stefan Kiefer, Andrzej S. Murawski, Joël Ouaknine, Björn Wachter, James WorrellAbstract:Deciding Equivalence of probabilistic automata is a key Problem for establishing various behavioural and anonymity properties of probabilistic systems. In recent experiments a randomised Equivalence test based on polynomial identity testing outperformed deterministic algorithms. In this paper we show that polynomial identity testing yields efficient algorithms for various generalisations of the Equivalence Problem. First, we provide a randomized NC procedure that also outputs a counterexample trace in case of inEquivalence. Second, we consider Equivalence of probabilistic cost automata. In these automata transitions are labelled with integer costs and each word is associated with a distribution on costs, corresponding to the cumulative costs of the accepting runs on that word. Two automata are equivalent if they induce the same cost distributions on each input word. We show that Equivalence can be checked in randomised polynomial time. Finally we show that the Equivalence Problem for probabilistic visibly pushdown automata is logspace equivalent to the Problem of whether a polynomial represented by an arithmetic circuit is identically zero.
-
On the Complexity of the Equivalence Problem for Probabilistic Automata
arXiv: Formal Languages and Automata Theory, 2011Co-Authors: Stefan Kiefer, Andrzej S. Murawski, Joël Ouaknine, Björn Wachter, James WorrellAbstract:Checking two probabilistic automata for Equivalence has been shown to be a key Problem for efficiently establishing various behavioural and anonymity properties of probabilistic systems. In recent experiments a randomised Equivalence test based on polynomial identity testing outperformed deterministic algorithms. In this paper we show that polynomial identity testing yields efficient algorithms for various generalisations of the Equivalence Problem. First, we provide a randomized NC procedure that also outputs a counterexample trace in case of inEquivalence. Second, we show how to check for Equivalence two probabilistic automata with (cumulative) rewards. Our algorithm runs in deterministic polynomial time, if the number of reward counters is fixed. Finally we show that the Equivalence Problem for probabilistic visibly pushdown automata is logspace equivalent to the Arithmetic Circuit Identity Testing Problem, which is to decide whether a polynomial represented by an arithmetic circuit is identically zero.
R I Podlovchenko - One of the best experts on this subject based on the ideXlab platform.
-
Equivalence Problem solvability in gateway program models
Automatic Control and Computer Sciences, 2014Co-Authors: R I Podlovchenko, A E MolchanovAbstract:Algebraic program models with procedures are designed to analyze program semantic properties on their models called program schemes. Liberisation and Equivalence Problems are stated for program models with procedures. A subclass of program models with procedures called special gateway models is investigated. A better complexity algorithm for the liberisation in such models is proposed. Primitive program schemes are defined as a subclass of the special gateway models. It is shown that the Equivalence Problem in such models is decidable if the Equivalence Problem is decidable in special program models without procedures. For some cases of decidability complexity is evaluated.
-
Technique of traces in solving the Equivalence Problem in algebraic program models
Cybernetics and Systems Analysis, 2009Co-Authors: R I PodlovchenkoAbstract:Algebraic models of sequential programs without procedures are considered. The question of applicability of the technique of traces to the solution of the Equivalence Problem in such models is investigated. Models called balanced left-cancellative semigroups are singled out for which the technique of traces provides an effective decision procedure.
-
on the Equivalence Problem for programs with mode switching
International Conference on Implementation and application of automata, 2005Co-Authors: R I Podlovchenko, Dmitry Rusakov, Vladimir A ZakharovAbstract:We study a formal model of imperative sequential programs and focus on the Equivalence Problem for some class of programs with mode switching whose runs can be divided into two stages. In the first stage a program selects an appropriate mode of computation. Several modes may be tried (switched) in turn before making the ultimate choice. Every time when the next mode is put to a test, the program brings data to some predefined state. In the second stage of the run, once a definite mode is fixed, the final result of computation is produced. We develop a new technique for simulating the behavior of such programs by means of finite automata and demonstrate that the Equivalence Problem for programs with mode switching is decidable within a polynomial space. By revealing a close relationships between the Equivalence Problem for this class of programs and the intersection emptiness Problem for deterministic finite automata we show that the the former is PSPACE-complete.
-
A New Approach to Solving Equivalence Problem
Programming and Computer Software, 2004Co-Authors: R I Podlovchenko, V. E. KhachatryanAbstract:An application of a new method for the Equivalence recognition in a computation model whose objects are labeled directed graphs is illustrated by the example of multitape automata. The paper is focused on general ideas of the method discussed. An algorithm that recognizes Equivalence of multitape automata with disjoint loops is described in detail.
Geraud Senizergues - One of the best experts on this subject based on the ideXlab platform.
-
Complete formal systems for Equivalence Problems
Theoretical Computer Science, 2000Co-Authors: Geraud SenizerguesAbstract:We describe four complete and recursively enumerable formal systems S0,D0,H0,B0. Each one of them proves the decidability of some Equivalence Problem for some class of automata: namely the language Equivalence Problem for simple automata, the language Equivalence Problem for deterministic pushdown automata, the function Equivalence Problem for deterministic pushdown transducers with outputs in an abelian group, the bisimulation Equivalence Problem for loop-free pushdown automata.
-
the Equivalence Problem for deterministic pushdown automata is decidable
International Colloquium on Automata Languages and Programming, 1997Co-Authors: Geraud SenizerguesAbstract:The Equivalence Problem for deterministic pushdown automata is shown to be decidable. We exhibit a complete formal system for deducing equivalent pairs of deterministic rational series on the alphabet associated with a dpda M.