McNaughton families of languages.
From MaRDI portal
Publication:1401181
DOI10.1016/S0304-3975(02)00070-1zbMATH Open1044.68082OpenAlexW1991636160MaRDI QIDQ1401181FDOQ1401181
Gundula Niemann, Martin Beaudry, Friedrich Otto, 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
Chomsky hierarchyClosure propertyString-rewritingChurch--Rosser languageMcNaughton familyMembership problem
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Pushdown automata with bounded nondeterminism and bounded ambiguity
- Problems complete for deterministic logarithmic space
- Complete problems for deterministic polynomial time
- Growing context-sensitive languages and Church-Rosser languages
- The Hardest Context-Free Language
- Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
- Infinite string rewrite systems and complexity
- Membership for growing context-sensitive grammars is polynomial
- Church-Rosser Thue systems and formal languages
- Some remarks on derivations in general rewriting systems
- On the Tape Complexity of Deterministic Context-Free Languages
- NTS languages are deterministic and congruential
- Monadic Thue systems
- On weakly confluent monadic string-rewriting systems
- Extensions to Barrington's M-program model
Cited In (10)
- Lambda-confluence for context rewriting systems
- Toward a theory of input-driven locally parsable languages
- Computing by observing: simple systems and simple observers
- DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
- Parikh-reducing Church-Rosser representations for some classes of regular languages
- The context-splittable normal form for Church-Rosser language systems.
- Lower bound technique for length-reducing automata
- MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS
- Locally Chain-Parsable Languages
- Regulated variants of limited context restarting automata
This page was built for publication: McNaughton families of languages.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401181)
