Degree-languages: A new concept of acceptance

DOI10.1016/S0022-0000(77)80012-3zbMath0354.68096OpenAlexW2000095412MaRDI QIDQ1236888

Detlef Wotschke

Publication date: 1977

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

Full work available at URL: https://doi.org/10.1016/s0022-0000(77)80012-3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (5)

The Boolean closure of linear context-free languages ⋮ Kernels of Sub-classes of Context-Free Languages ⋮ On the descriptional complexity of finite automata with modified acceptance conditions ⋮ Concise representations of regular languages by degree and probabilistic finite automata ⋮ Boolean kernels of context-free languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scattered context grammars
• Relationships between nondeterministic and deterministic tape complexities
• Time- and tape-bounded Turing acceptors and AFLs
• Tape-bounded Turing acceptors and principal AFLs
• Multitape finite automata with rewind instructions
• On certain formal properties of grammars
• Stack automata and compiling
• Control sets on grammars
• Two-way pushdown automata
• One-way stack automata
• Indexed Grammars—An Extension of Context-Free Grammars
• Programmed Grammars and Classes of Formal Languages
• Studies in abstract families of languages
• An infinite hierarchy of intersections of context-free languages

This page was built for publication: Degree-languages: A new concept of acceptance