McNaughton families of languages.

DOI10.1016/S0304-3975(02)00070-1zbMath1044.68082OpenAlexW1991636160MaRDI QIDQ1401181

Friedrich Otto, Gundula Niemann, Martin Beaudry, Markus Holzer

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00070-1

zbMATH Keywords

Chomsky hierarchyClosure propertyString-rewritingChurch--Rosser languageMcNaughton familyMembership problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (9)

Regulated variants of limited context restarting automata ⋮ Lower bound technique for length-reducing automata ⋮ Locally Chain-Parsable Languages ⋮ Computing by observing: simple systems and simple observers ⋮ MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS ⋮ The context-splittable normal form for Church-Rosser language systems. ⋮ Toward a theory of input-driven locally parsable languages ⋮ DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS ⋮ Lambda-confluence for context rewriting systems

Cites Work

• Membership for growing context-sensitive grammars is polynomial
• On weakly confluent monadic string-rewriting systems
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• NTS languages are deterministic and congruential
• Monadic Thue systems
• Extensions to Barrington's M-program model
• Complete problems for deterministic polynomial time
• Infinite string rewrite systems and complexity
• Growing context-sensitive languages and Church-Rosser languages
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Problems complete for deterministic logarithmic space
• Church-Rosser Thue systems and formal languages
• On the Tape Complexity of Deterministic Context-Free Languages
• The Hardest Context-Free Language
• Some remarks on derivations in general rewriting systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: McNaughton families of languages.