On shuffle products, acyclic automata and piecewise-testable languages
From MaRDI portal
Publication:1730033
DOI10.1016/j.ipl.2019.01.012zbMath1446.68081arXiv1810.02953OpenAlexW2894816735MaRDI QIDQ1730033
Simon Halfon, Philippe Schnoebelen
Publication date: 11 March 2019
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.02953
formal languagesshuffle productsubsequencesstar-free languagessubwordspiecewise-testable languagesdot-depth-one languages
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Languages of R-trivial monoids
- Classification of finite monoids: the language approach
- A generalization of finiteness
- Modeling literal morphisms by shuffle
- On Boolean combinations forming piecewise testable languages
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- Complexity of some problems from the theory of automata
- On Shuffle Ideals
- On biautomata
- The Height of Piecewise-Testable Languages with Applications in Logical Complexity
- Alternative Automata Characterization of Piecewise Testable Languages
- On free monoids partially ordered by embedding