Expressive capacity of subregular expressions

DOI10.1051/ITA/2018014MaRDI QIDQ5223616zbMATHOpenAlexWikidataFDO

Authors Martin Kutrib, Matthias Wendlandt

Publication date 18 July 2019

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1051/ita/2018014

zbMATH Keywords

characterizationsregular expressionsclosure propertiesstar-free languagesunion-free languagesconcatenation-free languagesexpressive capacitysubregular hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Concatenation-free languages
• Expressive capacity of concatenation freeness
• Structure and Complexity of Some Subregular Language Families
• Succinctness of the complement and intersection of regular expressions
• Succinctness of the Complement and Intersection of Regular Expressions

Cites work

• scientific article; zbMATH DE number 3694622 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 2086412 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Alternating finite automata and star-free languages
• Concatenation-free languages
• Dot-depth of star-free events
• Expressive capacity of concatenation freeness
• Expressive capacity of subregular expressions
• Isometries on positive operators of unit norm
• Nondeterministic state complexity of star-free languages
• On finite monoids having only trivial subgroups
• The Frobenius Problem and Its Generalizations
• The complexity of regular(-like) expressions

Cited in

(6)

• Expressive capacity of subregular expressions
• Expressivity of some versions of APAL
• Union-complexities of Kleene plus operation
• Concatenation-free languages
• Expressive capacity of concatenation freeness
• Union-Freeness Revisited — Between Deterministic and Nondeterministic Union-Free Languages

This page was built for publication: Expressive capacity of subregular expressions

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