Expressive capacity of subregular expressions

DOI10.1051/ITA/2018014zbMATH Open1475.68162OpenAlexW2914181013WikidataQ128538461 ScholiaQ128538461MaRDI QIDQ5223616FDOQ5223616

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• On finite monoids having only trivial subgroups
• Title not available (Why is that?)
• Dot-depth of star-free events
• Alternating finite automata and star-free languages
• Nondeterministic state complexity of star-free languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Frobenius Problem and Its Generalizations
• The complexity of regular(-like) expressions
• Expressive Capacity of Concatenation Freeness
• Expressive capacity of subregular expressions
• Isometries on positive operators of unit norm
• Concatenation-free languages

Cited In (4)

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

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)