Finite-Turn Pushdown Automata
From MaRDI portal
Cited in
(79)- On the power of deep pushdown stacks
- On reversal bounded alternating Turing machines
- Parallel complexity of logical query programs
- On a complexity hierarchy between L and NL
- Characterization and closure properties of linear \(\omega\)-languages
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- On recursion in ETOL systems
- The characterization of parallel ultralinear grammars by rational power series
- A pushdown automaton or a context-free grammar - which is more economical?
- Nonuniform complexity and the randomness of certain complete languages
- The decidability of a mapping problem for generalized sequential machines with final states
- One counter languages and the IRS condition
- Reversal-bounded multipushdown machines
- Familles de langages translatables et fermées par crochet
- Uniformly erasable AFL
- Context-free grammar forms
- Some uniformly erasable families of languages
- Control sets on context-free grammar forms
- One way finite visit automata
- On equivalence and subclass containment problems for deterministic context-free languages
- Context-free graph languages of bounded degree are generated by apex graph grammars
- Linear graph grammars: Power and complexity
- Ambiguity and decision problems for local adjunct languages
- Even linear simple matrix languages: formal language properties and grammatical inference.
- Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity
- Syntax checking either way
- Deterministic input-driven queue automata: finite turns, decidability, and closure properties
- Conjunctive grammars and alternating pushdown automata
- Finite turns and the regular closure of linear context-free languages
- Weighted iterated linear control
- Deep pushdown automata
- Derivation-bounded languages
- Principal AFL
- A characterization of context-free languages
- Finite-turn checking automata
- Substitution and bounded languages
- The complexity of ranking simple languages
- Boosting reversible pushdown machines by preprocessing
- Kernels of sub-classes of context-free languages
- A PUMPING CONDITION FOR ULTRALINEAR LANGUAGES
- Decidable subcases of the equivalence problem for recursive program schemes
- Iterated linear control and iterated one-turn pushdowns
- Descriptional complexity of bounded context-free languages
- scientific article; zbMATH DE number 3688749 (Why is no real title available?)
- Compelled operations and operations of degreeP
- Abstract families of context-free grammars
- Streaming algorithms for language recognition problems
- scientific article; zbMATH DE number 3776892 (Why is no real title available?)
- Sur la structure des langages algébriques
- On languages with a certain prefix property
- Simple context-free languages and free monadic recursion schemes
- Comparing language operations
- scientific article; zbMATH DE number 3602691 (Why is no real title available?)
- The complexity of the membership problem for some extensions of context-free languagest†
- Weightreducing grammars and ultralinear languages
- Sliding windows over context-free languages
- scientific article; zbMATH DE number 7439739 (Why is no real title available?)
- On the descriptional complexity of operations on semilinear sets
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- Synchronizing deterministic push-down automata can be really hard
- Queue Automata: Foundations and Developments
- Automata with two-sided pushdowns defined over free groups generated by reduced alphabets
- The theory of languages
- The theory of languages
- Basic tree transducers
- State grammars with stores
- Families of languages defined by ciliate bio-operations
- Familles de langages fermées par crochet ouvert
- Syntax checking either way
- Formal grammars for turn-bounded deterministic context-free languages
- Synchronizing deterministic push-down automata can be really hard
- Quasi-rocking real-time pushdown automata
- Turn complexity of context-free languages, pushdown and one-counter automata
- Power of counting by nonuniform families of polynomial-size finite automata
- Intersection and union hierarchies of deterministic context-free languages and pumping lemmas
- Kernels of context-free languages
- Language acceptors with a pushdown: characterizations and complexity
- Syntactic operators on full semiAFLs
- Look-ahead removal for total deterministic top-down tree transducers
This page was built for publication: Finite-Turn Pushdown Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5525346)
