The chop of languages

DOI10.1016/J.TCS.2017.02.002MaRDI QIDQ2358686zbMATH OpenOpenAlexFDO

Authors Markus Holzer, Sebastian Jakobi, Martin Kutrib

Publication date 15 June 2017

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

Full work available at URL https://doi.org/10.1016/j.tcs.2017.02.002

zbMATH Keywords

Chomsky hierarchycontext-free languagesdescriptional complexityregular languagesconcatenationclosure propertieslanguage classeschop operation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The chop of languages
• Fragments of language
• THE LANGUAGE OF CHAOS
• Unavoidable languages, cuts and innocent sets of words
• scientific article; zbMATH DE number 1692936
• Languages under concatenation and shuffling
• Mixed languages

Cites work

• scientific article; zbMATH DE number 3817058 (Why is no real title available?)
• scientific article; zbMATH DE number 3509706 (Why is no real title available?)
• scientific article; zbMATH DE number 2106353 (Why is no real title available?)
• scientific article; zbMATH DE number 3302285 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A helpful result for proving inherent ambiguity
• Chop expressions and discrete duration calculus
• Chop operations and expressions: descriptional complexity considerations
• Church-Rosser Thue systems and formal languages
• Closure and decidability properties of some language classes with respect to ciliate bio-operations.
• Descriptional complexity -- an introductory survey
• Developments in Language Theory
• Families of languages defined by ciliate bio-operations
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Generalized periodicity and primitivity for words
• Growing context-sensitive languages and Church-Rosser languages
• Homomorphisms that preserve star height
• Minimality in template-guided recombination
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• On Goedel speed-up and succinctness of language representations
• On the Succinctness of Different Representations of Languages
• On the descriptional power of heads, counters, and pebbles
• Reversal-bounded multipushdown machines
• Self-assembly of strings and languages
• Star height of certain families of regular events
• State complexity of regular languages
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• Transition graphs and the star-height of regular events

Cited in

(10)

• Descriptional complexity of chop operations on unary and finite languages
• scientific article; zbMATH DE number 7584602 (Why is no real title available?)
• More fragments of language.
• State complexity of overlap assembly
• Fragments of language
• State complexity of chop operations on unary and finite languages
• Site-directed insertion: language equations and decision problems
• The chop of languages
• Conjugate word blending: formal model and experimental implementation by XPCR
• Chop operations and expressions: descriptional complexity considerations

This page was built for publication: The chop of languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2358686)