Results 31 to 40 of about 3,110 (267)
Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
Моделирование и анализ информационных систем, 2020 Finite transducers, two-tape automata, and biautomata are related computational models descended from the concept of Finite-State Automaton. In these models an automaton controls two heads that read or write symbols on the tapes in the one-way mode.
Vladimir A. Zakharov
doaj +1 more source
The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 It is known that 2-state binary and 3-state unary probabilistic finite automata and 2-state unary quantum finite automata recognize uncountably many languages with cutpoints. These results have been obtained by associating each recognized language with a
Aleksejs Naumovs +2 more
doaj +1 more source
Finite automata over magmas: models and some applications in Cryptography [PDF]
Computer Science Journal of Moldova, 2018 In the paper the families of finite semi-automata and reversible finite Mealy and Moore automata over finite magmas are defined and analyzed in detail.
Volodymyr V. Skobelev +1 more
doaj
A Myhill-Nerode theorem for automata with advice [PDF]
Electronic Proceedings in Theoretical Computer Science, 2012 An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with ...
Alex Kruckman +3 more
doaj +1 more source
The reversibility of one-dimensional cellular automata
RUDN Journal of Engineering Research, 2021 Recently the reversible cellular automata are increasingly used to build high-performance cryptographic algorithms. The paper establishes a connection between the reversibility of homogeneous one-dimensional binary cellular automata of a finite size and ...
Alexey E. Zhukov
doaj +1 more source
Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, 1994 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
KAMINSKI, M., FRANCEZ, N.
openaire +1 more source
Testing the Equivalence of Regular Languages [PDF]
Electronic Proceedings in Theoretical Computer Science, 2009 The minimal deterministic finite automaton is generally used to determine regular languages equality. Antimirov and Mosses proposed a rewrite system for deciding regular expressions equivalence of which Almeida et al.
Marco Almeida +2 more
doaj +1 more source
Deciding the value 1 problem for probabilistic leaktight automata [PDF]
Logical Methods in Computer Science, 2015 The value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton, are there words accepted with probability arbitrarily close to 1?
Nathanaël Fijalkow +3 more
doaj +1 more source
Enumeration of finite automata
Information and Control, 1967 Harary ( 1960, 1964), in a survey of 27 unsolved problems in graphical enumeration, asked for the number of different finite automata. Recently, Harrison (1965) solved this problem, but without considering automata with initial and final states. With the aid of the Power Group Enumeration Theorem (Harary and Palmer, 1965, 1966) the entire problem can ...
Harary, Frank, Palmer, Edgar M.
openaire +2 more sources
FINITE AUTOMATA WITH ADVICE TAPES [PDF]
International Journal of Foundations of Computer Science, 2013 We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum.
Ugur Küçük +2 more
openaire +4 more sources