Absolutely parallel grammars and two-way finite-state transducers

DOI10.1016/S0022-0000(72)80025-4zbMath0246.68013MaRDI QIDQ2555753

Vaclav Rajlich

Publication date: 1972

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items

Equivalence problem of mappings relative to languages ⋮ Unnamed Item ⋮ Tree transducers, L systems, and two-way machines ⋮ Characterizations of regular and context-free matrices ⋮ 2DST mappings of languages and related problems ⋮ The string generating power of context-free hypergraph grammars ⋮ Iterated stack automata and complexity classes ⋮ Concatenation of graphs ⋮ Two-way A-transducers and AFL ⋮ Characterization theorems on abstract families of transducers ⋮ One way finite visit automata ⋮ Using acceptors as transducers ⋮ Classes of formal grammars ⋮ On two-way sequential transductions of full semi-AFL's ⋮ Some decision problems concerning sequential transducers and checking automata ⋮ Reasoning about strings in databases ⋮ Outils et résultats pour les transducteurs boustrophédons ⋮ Absolutely parallel grammars and two-way finite-state transducers ⋮ Three hierarchies of transducers ⋮ A note on Parikh maps, abstract languages, and decision problems

Cites Work

• Unnamed Item
• Unnamed Item
• Checking automata and one-way stack languages
• Scattered context grammars
• A characterization of two-way deterministic classes of languages
• Absolutely parallel grammars and two-way finite-state transducers
• On the Recognition of Primes by Automata
• One-way stack automata
• Preservation of languages by transducers
• Studies in abstract families of languages
• Two-way sequential transductions and stack automata