Regular Languages Definable by Majority Quantifiers with Two Variables
From MaRDI portal
Publication:3637216
DOI10.1007/978-3-642-02737-6_7zbMath1247.03066MaRDI QIDQ3637216
Stephanie Reifferscheid, Christoph Behle, Andreas Krebs
Publication date: 7 July 2009
Published in: Developments in Language Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-02737-6_7
68Q45: Formal languages and automata
03D05: Automata and formal grammars in connection with logical questions
Related Items
``Most of leads to undecidability: failure of adding frequencies to LTL, A Language-Theoretical Approach to Descriptive Complexity
Cites Work
- Nesting until and since in linear temporal logic
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Regular languages defined by generalized first-order formulas with a bounded number of bound variables
- Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids
- Amplifying lower bounds by means of self-reducibility
- Logic Meets Algebra: the Case of Regular Languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item