Degrees of streams

MaRDI QIDQ2855523zbMATH OpenFDO

Authors Jörg Endrullis, Dimitri Hendriks, Jan Willem Klop

Publication date 25 October 2013

Published in Integers (Search for Journal in Brave)

Full work available at URL http://www.emis.de/journals/INTEGERS/papers/a6num/a6num.Abstract.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Other degrees and reducibilities in computability and recursion theory (03D30) Formal languages and automata (68Q45)

Recommendations

• Transducer degrees: atoms, infima and suprema
• Degrees of transducibility
• scientific article; zbMATH DE number 3972194
• On the complexity of stream equality
• Degrees of infinite words, polynomials and atoms

Cited in

(15)

• A hierarchy for cuppable degrees
• Transducer degrees: atoms, infima and suprema
• Braids via term rewriting
• Degrees of Infinite Words, Polynomials and Atoms
• Degrees of transducibility
• The degree of squares is an atom
• Prefix-suffix square completion
• Degrees of infinite words, polynomials and atoms
• Ordering sequences by permutation transducers
• Decreasing diagrams for confluence and commutation
• A characterization of morphic words with polynomial growth
• Degree Monotone Paths
• Equality of streams is a \({\Pi}^0_2\)-complete problem
• Classifying all transducer degrees below N3
• A diamond structure in the transducer hierarchy

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Degrees of streams

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