scientific article; zbMATH DE number 3254905
From MaRDI portal
Publication:5541339
zbMATH Open0158.25404MaRDI QIDQ5541339FDOQ5541339
Authors: Michael O. Rabin, Dana Scott 
Publication date: 1959
Title of this publication is not available (Why is that?)
Cited In (only showing first 100 items - show all)
- 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
- Nondeterministic state complexity of star-free languages
- Nondeterministic state complexity of star-free languages
- The theory of languages
- Optimal simulation of self-verifying automata by deterministic automata
- Regular languages and Stone duality
- Fuzzy automata and languages
- Magic numbers in the state hierarchy of finite automata
- The equivalence problem of multitape finite automata
- Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
- State complexity of four combined operations composed of union, intersection, star and reversal
- Complexity of promise problems on classical and quantum automata
- The equivalence problem of multidimensional multitape automata
- Communication complexity method for measuring nondeterminism in finite automata
- More concise representation of regular languages by automata and regular expressions
- Comparing the size of NFAs with and without \(\epsilon\)-transitions
- Tree acceptors and some of their applications
- An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton
- Simple counter machines and number-theoretic problems
- Minimisation of acyclic deterministic automata in linear time
- Testing conformance of a deterministic implementation against a non-deterministic stream X-machine
- The Unmet Challenge of Timed Systems
- Über einen Automaten mit Pufferspeicherung
- A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
- Homomorphisms of algebras
- On the relevance of abstract algebra to control theory
- Parallel program schemata
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
- Pairs of complementary unary languages with ``balanced nondeterministic automata
- Polynomial complete problems in automata theory
- Complementing unary nondeterministic automata
- Descriptional complexity of input-driven pushdown automata
- Coping with selfish on-going behaviors
- Equivalence in automata theory based on complete residuated lattice-valued logic
- Powers of Regular Languages
- Automatic groups and amalgams
- Descriptional and computational complexity of finite automata -- a survey
- Determination of finite automata accepting subregular languages
- The partial clone of linear tree languages
- Prognosis of \(\omega\)-languages for the diagnosis of *-languages: a topological perspective
- Theory of átomata
- Boolean language operations on nondeterministic automata with a pushdown of constant height
- Deterministic blow-ups of minimal NFA's
- Two-Way Automata in Coq
- Stimulus-response theory of inite automata
- Size Complexity of Two-Way Finite Automata
- Finite-memory automata
- Determinization of ordinal automata
- Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
- The complementation problem for Büchi automata with applications to temporal logic
- Rigorous approximated determinization of weighted automata
- Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
- Weak Second‐Order Arithmetic and Finite Automata
- Program schemes, recursion schemes, and formal languages
- Complementing deterministic Büchi automata in polynomial time
- Finite automata and unary languages
- State-complexity of finite-state devices, state compressibility and incompressibility
- 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
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)
