A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
From MaRDI portal
Publication:3538848
DOI10.1142/S0129054108005802zbMath1157.03003MaRDI QIDQ3538848
Volker Diekert, Manfred Kufleitner, Paul Gastin
Publication date: 24 November 2008
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
surveyexpressibilitydecidabilitymonoidspiecewise testable languagesfactorization forestsfirst-order logic over finite words
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Subsystems of classical logic (including intuitionistic logic) (03B20)
Related Items (33)
Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words ⋮ First-order logic and its infinitary quantifier extensions over countable words ⋮ Level two of the quantifier alternation hierarchy over infinite words ⋮ The word problem for omega-terms over the Trotter-Weil hierarchy ⋮ On FO 2 Quantifier Alternation over Words ⋮ Measuring power of locally testable languages ⋮ The regular languages of wire linear \(\mathrm{AC}^0\) ⋮ The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy ⋮ Alternation Hierarchies of First Order Logic with Regular Predicates ⋮ Unnamed Item ⋮ Algebraic characterizations and block product decompositions for first order logic and its infinitary quantifier extensions over countable words ⋮ A survey on the local divisor technique ⋮ On Arch Factorization and Subword Universality for Words and Compressed Words ⋮ Language theoretical properties of hairpin formations ⋮ Forbidden Patterns for FO2 Alternation Over Finite and Infinite Words ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ Unnamed Item ⋮ On shuffle products, acyclic automata and piecewise-testable languages ⋮ Separating Without Any Ambiguity. ⋮ Fragments of first-order logic over infinite words ⋮ Level Two of the Quantifier Alternation Hierarchy over Infinite Words ⋮ Unnamed Item ⋮ The Height of Factorization Forests ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the index of Simon's congruence for piecewise testability ⋮ Unnamed Item ⋮ Separating regular languages with two quantifier alternations ⋮ Unnamed Item ⋮ The factorisation forest theorem ⋮ One quantifier alternation in first-order logic with modular predicates ⋮ Unnamed Item ⋮ Omega-rational expressions with bounded synchronization delay
Cites Work
- Categories as algebra: An essential ingredient in the theory of monoids
- Nesting until and since in linear temporal logic
- Factorization forests of finite height
- Definability with bounded number of bound variables
- First-order logic and star-free sets
- A property of the Schützenberger product
- Locally trivial categories and unambiguous concatenation
- Semigroups and languages of dot-depth two
- Partially ordered finite monoids and a theorem of I. Simon
- A generalization of the Schützenberger product of finite monoids
- Classification of finite monoids: the language approach
- Classifying regular events in symbolic logic
- Polynomial operations and hierarchies of concatenation
- On a conjecture concerning dot-depth two languages
- Some results on the dot-depth hierarchy
- The dot-depth hierarchy of star-free languages is infinite
- Sur le produit de concatenation non ambigu
- Temporal logic. 1st International Conference, ICTL '94, Bonn, Germany, July 11-14, 1994. Proceedings
- Polynomial closure and unambiguous product
- Regular languages defined by generalized first-order formulas with a bounded number of bound variables
- Expressive power of existential first-order sentences of Büchi's sequential calculus
- Logic, semigroups and automata on words
- Algebraic tools for the concatenation product.
- On factorization forests of finite height
- Finite semigroup varieties of the form V*D
- Graph congruences and wreath products
- On the expressive power of temporal logic
- A new algorithm for testing if a regular language is locally threshold testable
- Actions, wreath products of \(\mathcal C\)-varieties and concatenation product.
- First-order logic with two variables and unary temporal logic
- Dot-depth of star-free events
- Characterizations of locally testable events
- On the structure of semigroups
- Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy
- A conjecture on the concatenation product
- Weak Second‐Order Arithmetic and Finite Automata
- The complexity of propositional linear temporal logics
- INVERSE MONOIDS OF DOT-DEPTH TWO
- Some results onC-varieties
- Algebraic decision procedures for local testability
- A SYNTACTICAL PROOF OF LOCALITY OF DA
- On finite monoids having only trivial subgroups
This page was built for publication: A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
