Beyond \(\omega \)-regular languages: \(\omega T\)-regular expressions and their automata and logic counterparts

DOI10.1016/j.tcs.2019.12.029zbMath1433.68192MaRDI QIDQ1989336

Angelo Montanari, Dario Della Monica, Pietro Sala, David Barozzini, David de Frutos-Escrig

Publication date: 21 April 2020

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

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

zbMATH Keywords

counter automata; \(\omega \)-regular languages; \(\omega \)-regular expressions; monadic second-order logic of one successor

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weak MSO with the unbounding quantifier
• From liveness to promptness
• Prompt Interval Temporal Logic
• Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
• Interval Logics and ωB-Regular Languages
• Adding an Equivalence Relation to the Interval Logic ABB: Complexity and Expressiveness
• Computer Science Logic
• Separation Property for wB- and wS-regular Languages
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• Testing and generating infinite sequences by a finite automaton
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS