scientific article; zbMATH DE number 3254905

Publication date: 1959

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Related Items

The word problem for groups with regular relations. Improvement of the Knuth-Bendix algorithm ⋮ Testing conformance of a deterministic implementation against a non-deterministic stream X-machine ⋮ Progress measures, immediate determinacy, and a subset construction for tree automata ⋮ Two techniques in the area of the star problem in trace monoids ⋮ Equivalence in automata theory based on complete residuated lattice-valued logic ⋮ Finite-memory automata ⋮ Comparing the size of NFAs with and without \(\epsilon\)-transitions ⋮ Factor theory and the unity of opposites ⋮ Complexity results for two-way and multi-pebble automata and their logics ⋮ Finite automata capturing winning sequences for all possible variants of the \(PQ\) penny flip game ⋮ On the complexity of determinizing monitors ⋮ Regular language representations in the constructive type theory of Coq ⋮ Boolean language operations on nondeterministic automata with a pushdown of constant height ⋮ Control protocol synthesis for multi-agent systems with similar actions instantiated from agent and requirement templates ⋮ Some decisional problems on rational relations ⋮ From regular expressions to DFA's using compressed NFA's ⋮ The equivalence of stack-counter acceptors and quasi-realtime stack- counter acceptors ⋮ Program schemes, recursion schemes, and formal languages ⋮ Controlled pushdown automata ⋮ Fuzzy grammar theory based on lattices ⋮ Quasi-automatic semigroups ⋮ A family of NFAs which need 2\(^{n}-\alpha\) deterministic states ⋮ From bidirectionality to alternation. ⋮ Pairs of complementary unary languages with ``balanced nondeterministic automata ⋮ Determinization of fuzzy automata by factorizations of fuzzy states and right invariant fuzzy quasi-orders ⋮ Modeling of RNA secondary structures using two-way quantum finite automata ⋮ Descriptional complexity of limited automata ⋮ A note on the emptiness problem for alternating finite-memory automata ⋮ An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton ⋮ On the representation of finite deterministic 2-tape automata ⋮ Reversibility of computations in graph-walking automata ⋮ An algebraic characterization of deterministic regular languages over infinite alphabets. ⋮ Theory of átomata ⋮ Magic numbers in the state hierarchy of finite automata ⋮ Hybrid one-dimensional reversible cellular automata are regular ⋮ Reachability analysis of reversal-bounded automata on series-parallel graphs ⋮ Epistemic GDL: a logic for representing and reasoning about imperfect information games ⋮ Effectful applicative similarity for call-by-name lambda calculi ⋮ Reversibility of general 1D linear cellular automata over the binary field \(\mathbb{Z}_2\) under null boundary conditions ⋮ New size hierarchies for two way automata ⋮ Removing nondeterminism in constant height pushdown automata ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ Angelic processes for CSP via the UTP ⋮ Decidability and syntactic control of interference ⋮ On the descriptional complexity of finite automata with modified acceptance conditions ⋮ State complexity of some operations on binary regular languages ⋮ Complementing unary nondeterministic automata ⋮ The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata ⋮ On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's ⋮ Determination of finite automata accepting subregular languages ⋮ Oblivious DFA evaluation on joint input and its applications ⋮ Finite automata with multiplication ⋮ The inclusion problem for simple languages ⋮ ``V-tape, a virtual memory oriented data type, and its resource requirements ⋮ Regular subsets in semi-direct products of monoids ⋮ One way finite visit automata ⋮ Inference for regular bilanguages ⋮ Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes ⋮ On two-way sequential transductions of full semi-AFL's ⋮ Natural strategic ability ⋮ Sequential fuzzy system identification ⋮ Some decision problems concerning sequential transducers and checking automata ⋮ On approximate enhanced covers under Hamming distance ⋮ Automata theory and control theory - a rapprochement ⋮ Characterizing derivation trees of context-free grammars through a generalization of finite automata theory ⋮ Some definitional suggestions for automata theory ⋮ Maximin sequential chains ⋮ On a characterization of the nonregular set of primes ⋮ Referenced automata and metaregular families ⋮ Stimulus-response theory of inite automata ⋮ Regular expressions and the equivalence of programs ⋮ Maximin, Minimax, and composite sequential machines ⋮ Über einen Automaten mit Pufferspeicherung ⋮ Übertragung automatentheoretischer Sätze auf Chomsky-Sprachen ⋮ Reflections on the phenomenon of Aleksej Andreevich Lyapunov ⋮ Parallel program schemata ⋮ Writing pushdown acceptors ⋮ On the relevance of abstract algebra to control theory ⋮ REF-ARF: A system for solving problems stated as procedures ⋮ Membrane automata for modeling biomolecular processes ⋮ Sets recognized by n-tape automata ⋮ Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Automata and rational expressions ⋮ Finite transducers and rational transductions ⋮ Descriptional complexity of regular languages ⋮ Černý's conjecture and the road colouring problem ⋮ On the transformation semigroups of finite automata ⋮ Polynomial complete problems in automata theory ⋮ The partial clone of linear tree languages ⋮ Ambiguity and decision problems for local adjunct languages ⋮ Halbgruppen und Automaten ⋮ Automata, Boolean matrices, and ultimate periodicity. ⋮ Alternation and bounded concurrency are reverse equivalent. ⋮ Communication complexity method for measuring nondeterminism in finite automata ⋮ On the boundary of regular languages ⋮ Time-aware uniformization of winning strategies ⋮ Modelization of deterministic rational relations ⋮ Distances between languages and reflexivity of relations ⋮ More on deterministic and nondeterministic finite cover automata ⋮ Ramsey-Based Inclusion Checking for Visibly Pushdown Automata ⋮ Decision Problems of Finite Automata Design and Related Arithmetics ⋮ The theory of languages ⋮ Stone Duality and the Recognisable Languages over an Algebra ⋮ Operations on Permutation Automata ⋮ Descriptional Complexity of Input-Driven Pushdown Automata ⋮ State-complexity of finite-state devices, state compressibility and incompressibility ⋮ Unnamed Item ⋮ Homomorphisms of algebras ⋮ Automata Theory and Model Checking ⋮ Transfer of Model Checking to Industrial Practice ⋮ On the capabilities of systolic systems ⋮ Automatic construction of test sets: Theoretical approach ⋮ Bounded Regular Sets ⋮ Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines ⋮ Sufficient conditions of equivalence of three-tape automata ⋮ Geodesic growth in virtually abelian groups ⋮ Loops in automata and HDTOL relations ⋮ Two-way deterministic automata with jumping mode ⋮ A geometrical view of the determinization and minimization of finite-state automata ⋮ Programs=data=first-class citizens in a computational world ⋮ Regular canonical systems ⋮ On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages ⋮ Complexity of Promise Problems on Classical and Quantum Automata ⋮ Kleene closure and state complexity ⋮ A Note on Pushdown Store Automata and Regular Systems ⋮ Unnamed Item ⋮ Stochastic grammars and languages ⋮ Unnamed Item ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Left-noncounting languages ⋮ Input- or output-unary sweeping transducers are weaker than their 2-way counterparts ⋮ Two-way representations and weighted automata ⋮ General Framework ⋮ Learning two-tape automata from queries and counterexamples ⋮ Spiking Neural P Systems with Thresholds ⋮ Descriptional Complexity of the Forever Operator ⋮ Weak Second‐Order Arithmetic and Finite Automata ⋮ Complexity results for multi-pebble automata and their logics ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ Formalization of the concept of multitape automaton ⋮ The Unmet Challenge of Timed Systems ⋮ A state space approach to the finite automata ⋮ On Stateless Deterministic Restarting Automata ⋮ Unnamed Item ⋮ From Philosophical to Industrial Logics ⋮ Nondeterministic State Complexity of Star-Free Languages ⋮ State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal ⋮ Note on Reversal of Binary Regular Languages ⋮ Unnamed Item ⋮ Regular sets and finite automata over?-groups ⋮ One-Time Nondeterministic Computations ⋮ Tighter Bounds for the Determinisation of Büchi Automata ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Converting Self-verifying Automata into Deterministic Automata ⋮ Better Hyper-minimization ⋮ The conjugacy problem for Higman’s group ⋮ Both Ways Rational Functions ⋮ Exposing graph uniformities via algebraic specification ⋮ Language Recognition Power and Succinctness of Affine Automata ⋮ The complexity of concatenation on deterministic and alternating finite automata ⋮ On the power of two-way multihead quantum finite automata ⋮ Size Complexity of Two-Way Finite Automata ⋮ Powers of Regular Languages ⋮ Magic Numbers and Ternary Alphabet ⋮ An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton ⋮ A more efficient notion of zigzag stability ⋮ On Repetition Languages ⋮ Concatenation of Regular Languages and Descriptional Complexity ⋮ Domain mu-calculus ⋮ On formalised computer programs ⋮ Equivalences on program schemes ⋮ Substitution in families of languages ⋮ Tree acceptors and some of their applications ⋮ Zur Theorie der nichtdeterministischen und unvollständigen Automaten ⋮ Quantum Automata Theory – A Review ⋮ Two-Way Automata in Coq ⋮ Real-time computations with restricted nondeterminism ⋮ Self-Verifying Finite Automata and Descriptional Complexity ⋮ The Complexity of Languages Resulting from the Concatenation Operation ⋮ Der programmierbare endliche Automat. (The programmable finite automaton) ⋮ AFL with the semilinear property ⋮ Classification of noncounting events ⋮ Unnamed Item ⋮ System identification via state characterization ⋮ Free and almost-free subsemigroups of a free semigroup ⋮ Solvable classes of discrete dynamic programming ⋮ Some Remarks on Abstract Machines ⋮ Deterministic blow-ups of minimal NFA's ⋮ The Developments of the Concept of Machine Computability from 1936 to the 1960s ⋮ Decision problems among the main subfamilies of rational relations ⋮ The many faces of a translation ⋮ Proof-directed program transformation: A functional account of efficient regular expression matching ⋮ On the Decidability of the Equivalence Problem for Monadic Recursive Programs ⋮ How Deterministic are Good-For-Games Automata? ⋮ La théorie des fonctions récursives et ses applications. (Exposé d'information générale) ⋮ A note on undecidable properties of formal languages ⋮ Control sets on grammars ⋮ Permutation automata ⋮ Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata ⋮ Canonical systems which produce periodic sets ⋮ The theory of languages ⋮ Direct and subdirect product structure theorems for non-deterministic automata ⋮ On ywo-way, two-tape automata ⋮ An asymmetric regular set ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Affine Computation and Affine Automaton ⋮ Abstract families of relations ⋮ Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata ⋮ Subset construction complexity for homogeneous automata, position automata and ZPC-structures ⋮ A New Hierarchy for Automaton Semigroups ⋮ Improved algorithms for computing the greatest right and left invariant Boolean matrices and their application ⋮ Notes on finitely generated semigroups and pumping conditions for regular languages ⋮ The complementation problem for Büchi automata with applications to temporal logic ⋮ The problem of equivalent transformations for homogeneous multitape automata ⋮ Prognosis of \(\omega\)-languages for the diagnosis of *-languages: a topological perspective ⋮ The state complexity of \(L^{2}\) and \(L^k\) ⋮ Factorization forests for infinite words and applications to countable scattered linear orderings ⋮ Computing equilibria: a computational complexity perspective ⋮ Finite automata and unary languages ⋮ On a subclass of \(\infty\)-regular languages ⋮ Transition systems, metric spaces and ready sets in the semantics of uniform concurrency ⋮ On size reduction techniques for multitape automata ⋮ Concatenation of inputs in a two-way automaton ⋮ A note on the reduction of two-way automata to one-way automata ⋮ Complementing deterministic Büchi automata in polynomial time ⋮ On probabilistic analog automata ⋮ Determinization of ordinal automata ⋮ Rigorous approximated determinization of weighted automata ⋮ On stateless deterministic restarting automata ⋮ Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata ⋮ State complexity of star of union and square of union on \textit{k} regular languages ⋮ Simple counter machines and number-theoretic problems ⋮ A hierarchy of deterministic languages ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Algorithms and topology of Cayley graphs for groups. ⋮ Prefix-free languages: left and right quotient and reversal ⋮ Profile trees for Büchi word automata, with application to determinization ⋮ Size complexity of rotating and sweeping automata ⋮ Vector addition systems and regular languages ⋮ On inclusion problem for deterministic multitape automata ⋮ Construction of minimal deterministic finite automata from biological motifs ⋮ Coping with selfish on-going behaviors ⋮ Regular languages with variables on graphs ⋮ State complexity of union and intersection of star on \(k\) regular languages ⋮ A note on decision problems for three-way two-dimensional finite automata ⋮ Finite automata theory with membership values in lattices ⋮ Probabilistic contracts: a compositional reasoning methodology for the design of systems with stochastic and/or non-deterministic aspects ⋮ On multi-head automata with restricted nondeterminism ⋮ Concatenation of regular languages and descriptional complexity ⋮ Endmarkers can make a difference ⋮ Nondeterministic state complexity of star-free languages ⋮ An alternating hierarchy for finite automata ⋮ Reversal of binary regular languages ⋮ Quasiidentities in a free semigroup ⋮ Parallel complexity of the regular code problem ⋮ New techniques for proving the decidability of equivalence problem ⋮ Projections of languages recognizable by probabilistic and alternating finite multitape automata ⋮ Postfix automata ⋮ Automatic groups and amalgams ⋮ Partial derivatives of regular expressions and finite automaton constructions ⋮ The dual equivalence of equations and coequations for automata ⋮ The relativized relationship between probabilistically checkable debate systems, IP and PSPACE ⋮ Regular languages and Stone duality ⋮ Minimisation of acyclic deterministic automata in linear time ⋮ On the equivalence of recursive and nonrecursive Datalog programs ⋮ Walking on data words ⋮ Finite automata on directed graphs ⋮ Multiplicities: A deterministic view of nondeterminism ⋮ 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 ⋮ The equivalence problem of multidimensional multitape automata ⋮ Infinite trees and automaton-definable relations over \(\omega\)-words ⋮ The operation \(\uparrow\) on formal power series ⋮ More concise representation of regular languages by automata and regular expressions ⋮ Rewriting of regular expressions and regular path queries ⋮ Myhill-Nerode type theory for fuzzy languages and automata ⋮ Theories of automata on \(\omega\)-tapes: a simplified approach ⋮ Fuzzy neural networks ⋮ Two-way unary automata versus logarithmic space ⋮ Some free submonoids of the free monoid of prefix codes ⋮ Alternating states for dual nondeterminism in imperative programming ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Optimal simulation of self-verifying automata by deterministic automata ⋮ Realizations of fuzzy languages by probabilistic, max-product, and maximin automata ⋮ A note on autodense related languages ⋮ Adjoint machines, state-behavior machines, and duality ⋮ Nondeterministic fuzzy automata ⋮ Sequentielle Analyse kontextfreier Sprachen ⋮ The complexity of asynchronous model based testing ⋮ Rational relations having a rational trace on each finite intersection of rational relations ⋮ State complexity of union and intersection of square and reversal on \(k\) regular languages ⋮ Prefix-primitive annihilators of languages under some operations ⋮ Fuzzy automata and languages ⋮ A characterization of automata and a direct product decomposition ⋮ On the structure of Abelian automata ⋮ Checking experiments for stream X-machines ⋮ From regular expressions to deterministic automata ⋮ HDTOL matching of computations of multitape automata ⋮ The zig-zag power series: A two-way version of the \({}^*\) operator. ⋮ Syntactic operators on full semiAFLs ⋮ The equivalence problem for deterministic two-tape automata ⋮ Equivalence of regular expressions over a partially commutative alphabet ⋮ On input-revolving deterministic and nondeterministic finite automata ⋮ Polynomial algorithm for equivalence problem of deterministic multitape finite automata ⋮ The inclusion problem for some classes of deterministic multitape automata ⋮ Equivalence of infinite behavior of finite automata ⋮ The equivalence problem of multitape finite automata ⋮ A note on Parikh maps, abstract languages, and decision problems ⋮ Another generalization of Higman's well quasi order result on \(\Sigma ^*\)