First-order properties of trees, star-free expressions, and aperiodicity

DOI10.1051/ita/1991250201251zbMath0741.68065OpenAlexW57066809MaRDI QIDQ3978766

Uschi Heuter

Publication date: 25 June 1992

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92385

zbMATH Keywords

tree automatafirst-order definabilitytree languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items

Modulo-counting quantifiers over finite trees ⋮ First-order logic on finite trees ⋮ Adjunct Elimination in Context Logic for Trees ⋮ Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages ⋮ Aperiodicity in Tree Automata ⋮ Operator precedence temporal logic and model checking ⋮ ALGEBRAIC CHARACTERIZATION OF LOGICALLY DEFINED TREE LANGUAGES ⋮ Adjunct elimination in context logic for trees ⋮ Unnamed Item ⋮ General varieties of tree languages ⋮ Algebra for trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classifying regular events in symbolic logic
• Tree acceptors and some of their applications
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• On finite monoids having only trivial subgroups
• Generalized finite automata theory with an application to a decision problem of second-order logic
• A Note on Star-Free Events