Bounded fixed-point definability and tabular recognition of languages

DOI10.1007/3-540-61377-3_50MaRDI QIDQ6560180zbMATH OpenFDO

Authors Hans Leiß

Publication date 21 June 2024

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On efficient recognition of transductions and relations
• scientific article; zbMATH DE number 1670480
• First-order definable languages
• scientific article; zbMATH DE number 3958761
• On the expressive power of FO[+]

Cites work

• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 408802 (Why is no real title available?)
• scientific article; zbMATH DE number 2079028 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• Alternation
• An efficient recognizer for the Boolean closure of context-free languages
• Fast uniform analysis of Coupled-Context-Free languages
• On multiple context-free grammars
• Relational queries computable in polynomial time

Cited in

(1)

• Some questions on polynomially computable representations for generating grammars and Backus-Naur forms

This page was built for publication: Bounded fixed-point definability and tabular recognition of languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6560180)