scientific article; zbMATH DE number 3254906
From MaRDI portal
zbMath0158.25601MaRDI QIDQ5541340
Publication date: 1959
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Automates et codes zigzag, A linear-time simulation of deterministic \(d\)-limited automata, State-complexity of finite-state devices, state compressibility and incompressibility, Finite-memory automata, Alternating two-way AC-tree automata, Two-way and one-way quantum and classical automata with advice for online minimization problems, Some results concerning two-dimensional turing machines and finite automata, The equivalence of pebbles and sensing heads for finite automata, Complexity results for two-way and multi-pebble automata and their logics, Complexity of probabilistic versus deterministic automata, Concatenation of inputs in a two-way automaton, A note on the reduction of two-way automata to one-way automata, Regular language representations in the constructive type theory of Coq, Two-way automaton computations, Two-way deterministic automata with jumping mode, Complexity of Promise Problems on Classical and Quantum Automata, State succinctness of two-way finite automata with quantum and classical states, On the decidability of the valuedness problem for two-way finite transducers, From Two-Way to One-Way Finite Automata—Three Regular Expression-Based Methods, Characterization of context-pree languages by erasing automata, Complexity of multi-head finite automata: origins and directions, Pebble minimization: the last theorems, Unnamed Item, Weighted two-way transducers, From bidirectionality to alternation., Weighted two-way transducers, Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic, Energy complexity of computation, Two-Way Non-Uniform Finite Automata, On the transformation of two-way finite automata to unambiguous finite automata, Once-Marking and Always-Marking 1-Limited Automata, On the complexity of regular-grammars with integer attributes, Modeling of RNA secondary structures using two-way quantum finite automata, Deciding FO-definability of regular languages, Input- or output-unary sweeping transducers are weaker than their 2-way counterparts, Two-way representations and weighted automata, Descriptional complexity of limited automata, Loops and overloops for tree-walking automata, An alternating hierarchy for finite automata, Unnamed Item, Two-way automata and length-preserving homomorphisms, More Concise Representation of Regular Languages by Automata and Regular Expressions, Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal, Turing machines and bimachines, Aperiodic String Transducers, Complexity results for multi-pebble automata and their logics, Translation from classical two-way automata to pebble two-way automata, On the transformation of two-way deterministic finite automata to unambiguous finite automata, A note on the space complexity of some decision problems for finite automata, One-way resynchronizability of word transducers, On the state complexity of operations on two-way finite automata, New size hierarchies for two way automata, Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations, The operation \(\uparrow\) on formal power series, Removing nondeterminism in constant height pushdown automata, More concise representation of regular languages by automata and regular expressions, Two-way automata versus logarithmic space, Pebble Weighted Automata and Weighted Logics, Linear-time limited automata, Two-way unary automata versus logarithmic space, Unbounded-error quantum computation with small space bounds, Attribute grammars for unranked trees as a query language for structured documents, Unnamed Item, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity, Sequences of words defined by two-way transducers, Regular Transformations of Data Words Through Origin Information, Unnamed Item, Two-way pebble transducers for partial functions and their composition, Aperiodic String Transducers, Efficient probability amplification in two-way quantum finite automata, The zig-zag power series: A two-way version of the \({}^*\) operator., Size Complexity of Two-Way Finite Automata, A more efficient notion of zigzag stability, Register Transducers Are Marble Transducers, Origin-equivalence of two-way word transducers is in PSPACE, Regular transducer expressions for regular transformations, Two-Way Automata in Coq, A characterization of two-way deterministic classes of languages, Der programmierbare endliche Automat. (The programmable finite automaton), Unnamed Item, Descriptional complexity of regular languages, Deterministic one-way simulation of two-way deterministic finite automata over small alphabets, On the Class of Predicates Decidable by Two-Way Multitape Finite Automata, The many faces of a translation, Automates boustrophédon et mots infinis, Converting nondeterministic two-way automata into small deterministic linear-time machines, Query automata over finite trees, Computation with multiple CTCs of fixed length and width, Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
