scientific article; zbMATH DE number 3254905

zbMATH Open0158.25404MaRDI QIDQ5541339FDOQ5541339

Authors: Michael O. Rabin, Dana Scott 

Publication date: 1959

Title of this publication is not available (Why is that?)

zbMATH Keywords

mathematical logic

Cited In (only showing first 100 items - show all)

• Translation from classical two-way automata to pebble two-way automata
• Realizations of fuzzy languages by probabilistic, max-product, and maximin automata
• The operation \(\uparrow\) on formal power series
• The zig-zag power series: A two-way version of the \({}^*\) operator.
• Stone duality and the recognisable languages over an algebra
• Infinite trees and automaton-definable relations over \(\omega\)-words
• The equivalence of stack-counter acceptors and quasi-realtime stack- counter acceptors
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• Factorization forests for infinite words and applications to countable scattered linear orderings
• From regular expressions to DFA's using compressed NFA's
• Canonical systems which produce periodic sets
• A note on undecidable properties of formal languages
• New size hierarchies for two way automata
• On the equivalence of recursive and nonrecursive Datalog programs
• Prefix-primitive annihilators of languages under some operations
• Rational relations having a rational trace on each finite intersection of rational relations
• Another generalization of Higman's well quasi order result on \(\Sigma ^*\)
• Affine computation and affine automaton
• Control sets on grammars
• Magic Numbers and Ternary Alphabet
• The theory of languages
• HDTOL matching of computations of multitape automata
• The equivalence problem for deterministic two-tape automata
• On probabilistic analog automata
• Membrane automata for modeling biomolecular processes
• On a characterization of the nonregular set of primes
• REF-ARF: A system for solving problems stated as procedures
• Syntactic operators on full semiAFLs
• The inclusion problem for some classes of deterministic multitape automata
• Descriptional complexity of limited automata
• Descriptional and Computational Complexity of Finite Automata
• One way finite visit automata
• Self-verifying finite automata and descriptional complexity
• Regular canonical systems
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• A geometrical view of the determinization and minimization of finite-state automata
• An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton
• Postfix automata
• Construction of minimal deterministic finite automata from biological motifs
• Complexity results for two-way and multi-pebble automata and their logics
• Two-way unary automata versus logarithmic space
• Concatenation of inputs in a two-way automaton
• On stateless deterministic restarting automata
• Automata, Boolean matrices, and ultimate periodicity.
• Sets recognized by n-tape automata
• Probabilistic contracts: a compositional reasoning methodology for the design of systems with stochastic and/or non-deterministic aspects
• Concatenation of regular languages and descriptional complexity
• Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes
• A Note on Pushdown Store Automata and Regular Systems
• From regular expressions to deterministic automata
• Classification of noncounting events
• The dual equivalence of equations and coequations for automata
• Walking on data words
• Permutation automata
• Computing equilibria: a computational complexity perspective
• Quantum automata theory -- a review
• Dynamical systems in categories
• On the state complexity of operations on two-way finite automata
• Two double-exponential gaps for automata with a limited pushdown
• Quantum finite automata: advances on Bertoni's ideas
• Some definitional suggestions for automata theory
• Regular expressions and the equivalence of programs
• Equivalences on program schemes
• On formalised computer programs
• Writing pushdown acceptors
• The relativized relationship between probabilistically checkable debate systems, IP and PSPACE
• On the Decidability of the Equivalence Problem for Monadic Recursive Programs
• State complexity of star of union and square of union on \textit{k} regular languages
• State complexity of union and intersection of star on \(k\) regular languages
• Reversal of binary regular languages
• Loops in automata and HDTOL relations
• Rewriting of regular expressions and regular path queries
• Bounded Regular Sets
• On Stateless Deterministic Restarting Automata
• Algorithms and topology of Cayley graphs for groups.
• An algebraic characterization of deterministic regular languages over infinite alphabets.
• Real-time computations with restricted nondeterminism
• Decision Problems of Finite Automata Design and Related Arithmetics
• Theories of automata on \(\omega\)-tapes: a simplified approach
• Automatic construction of test sets: theoretical approach
• Spiking Neural P Systems with Thresholds
• The state complexity of \(L^{2}\) and \(L^k\)
• Partial derivatives of regular expressions and finite automaton constructions
• A note on the reduction of two-way automata to one-way automata
• Size complexity of rotating and sweeping automata
• Regular languages with variables on graphs
• The inclusion problem for simple languages
• Nondeterministic fuzzy automata
• State complexity of union and intersection of square and reversal on \(k\) regular languages
• Adjoint machines, state-behavior machines, and duality
• Finite automata theory with membership values in lattices
• On multi-head automata with restricted nondeterminism
• State complexity of some operations on binary regular languages
• The complexity of asynchronous model based testing
• Complexity of multi-head finite automata: origins and directions
• Distances between languages and reflexivity of relations
• Tighter Bounds for the Determinisation of Büchi Automata
• Myhill-Nerode type theory for fuzzy languages and automata
• Checking experiments for stream X-machines
• An alternating hierarchy for finite automata

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5541339)