Morphic characterizations of languages in Chomsky hierarchy with insertion and locality

DOI10.1016/J.IC.2010.11.011MaRDI QIDQ553307zbMATH OpenOpenAlexFDO

Authors Kaoru Fujioka

Publication date 27 July 2011

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2324/25741

zbMATH Keywords

insertion systemstrictly locally testable language

Mathematics Subject Classification ID

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

Review text

Using strictly locally testable languages and morphisms new characterisations of languages in Chomsky hierarchy are proved.

Recommendations

• New Morphic Characterizations of Languages in Chomsky Hierarchy Using Insertion and Locality
• Morphic characterizations with insertion systems controlled by a context of length one
• Morphic Characterizations in Terms of Insertion Systems with a Context of Length One
• REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS
• Morphic characterizations of language families in terms of insertion systems and star languages

Cites work

• Characterizations of recursively enumerable languages by means of insertion grammars
• Context-free insertion-deletion systems
• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• New Morphic Characterizations of Languages in Chomsky Hierarchy Using Insertion and Locality
• REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS
• Splicing representations of stricly locally testable languages

Cited in

(10)

• Morphic characterizations with insertion systems controlled by a context of length one
• On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
• \(\mathcal{L}\)-reduction computation revisited
• Finite automata with multiset memory: a new characterization of Chomsky hierarchy
• Morphic characterizations of language families in terms of insertion systems and star languages
• REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS
• New Morphic Characterizations of Languages in Chomsky Hierarchy Using Insertion and Locality
• scientific article; zbMATH DE number 17554 (Why is no real title available?)
• Morphic characterizations of language families based on local and star languages
• Morphic Characterizations in Terms of Insertion Systems with a Context of Length One

This page was built for publication: Morphic characterizations of languages in Chomsky hierarchy with insertion and locality

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