Deciding FO-definability of regular languages
From MaRDI portal
Publication:2695357
DOI10.1007/978-3-030-88701-8_15OpenAlexW3210510245MaRDI QIDQ2695357
Agi Kurucz, Yury Savateev, Vladislav Ryzhikov, Michael Zakharyashchev
Publication date: 30 March 2023
Full work available at URL: https://arxiv.org/abs/2105.06202
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Boolean function complexity. Advances and frontiers.
- Explicit bounds for primes in arithmetic progressions
- Finite-automaton aperiodicity is PSPACE-complete
- A note on the reduction of two-way automata to one-way automata
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Regular languages in \(NC\)
- First-order rewritability of ontology-mediated queries in linear temporal logic
- Weak Second‐Order Arithmetic and Finite Automata
- The intersection problem for finite monoids
- Complexity of some problems from the theory of automata
- Decision Problems of Finite Automata Design and Related Arithmetics
- The membership problem in aperiodic transformation monoids
- SOLVABILITY OF FINITE GROUPS VIA CONDITIONS ON PRODUCTS OF 2-ELEMENTS AND ODD p-ELEMENTS
- On finite monoids having only trivial subgroups
- Linking Data to Ontologies
- Nonsolvable finite groups all of whose local subgroups are solvable
- Deciding FO-Rewritability of Ontology-Mediated Queries in Linear Temporal Logic
This page was built for publication: Deciding FO-definability of regular languages
