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